C++ O(n) solution with thought process applying simple bucket theory


  • 40

    The brute force solution can definitely lead us to the right answer just by doing too many redundant comparisons. When two pointer approach comes to mind, it is intuitive to set both pointers i, j at each end of this array, and move them strategically to the middle of array, update the answer during this process return the answer when we reach the end of array. Suppose now we have the scenarios below:

    7, 5, 6, 9
    
    i        j
    

    When i = 1, j = 4,

    ans = min(7, 9) * (4 - 1) = 21 
    

    What's next? Should we move i or j? We notice that to calculate the area, the height is really identified by the smaller number / shorter end between the two ends, since it's required that you may not slant the water, so it sounds like Bucket theory: how much water a bucket can contain depends on the shortest plank. So, as to find the next potential maximum area, we disregard the shorter end by moving it to the next position. So in the above case, the next status is to move i to the left,

    7, 5, 6, 9
    
       i     j
    

    update:

    area (i, j) = area(2, 4) = min(5, 9) * (4 - 2) = 10
    ans = max(21, 10) = 21
    

    You may notice that, if we move j instead, you actually get a larger area for length of 2:

    area (i, j) = area(1, 3) = min(7, 6) * (3 - 1) = 18
    

    Does that mean this approach will not work? If you look at this way, we move pointer as to get the next potential max, so it doesn't need to be the maximum for all combinations with length l. Even though 18 is greater than 10, it's smaller than 21 right? So don't worry, we can move on to find the next potential maximum result. Now we need to prove, why disregard the shorter end can safely lead us to the right answer by doing a little maths.

    Given an array: a1, a2, a3, a4, ai, ......, aj, ......, an
                                     i           j
    

    Assume the maximum area so far is ans, we prove that

    "By moving shorter end pointer further doesn't eliminate the final answer (with two ends at maxi, maxj respectively) in our process"
    

    Suppose we have two ends at (i, j) respectively at this moment:

    (i) If the final answer equals what we have already achieved, it's done! In this scenario, we must have

    maxi <= i, maxj >= j 
    

    (ii) Otherwise, we know as we move any pointer further, the length of the next rectangle decreases, so the height needs to increase as to result in a larger area. So we have

    min(height[maxi], height[maxj]) > min(height[i], height[j]) 
    

    So the smaller one in height[i], height[j] won't become any end in the maximum rectangle, so it's safe to move forward without it.

    Till now, it has been proved that this approach can work in O(n) time since we advance one end towards the middle in each iteration, and update ans takes constant time in each iteration.

    class Solution {
    public:
        int maxArea(vector<int>& height) {
            int ans = 0;
            int i = 0, j = height.size() - 1;          
            while(i < j){
                ans = max(ans, (j - i) * min(height[i], height[j]));
                height[i] > height[j] ? j-- : i++;  
            }
            
            return ans;
        }
    };

  • 0
    F

    Great idea, way cleaner than my first implementation. (I tried to skip non-increasing sequence from each end, still O(n) but too long)
    Here is an even conciser version of your idea:

    int maxArea(vector<int>& h) 
    {
    	int m = 0;
    	for(int i = 0, j = h.size() - 1; i < j; m = max(m, (h[i] < h[j] ? h[i ++] : h[j --]) * (j - i + 1)));
    	return m;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.