leetcode Question 22: Container With Most Water


Container With Most Water
Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.


Analysis:
An easy but time-consuming way to solve this problem is of O(n^2), compare the area for each pair of points. However, it cannot pass the large test.
There is a greedy way to solve this problem in O(n). Use two pointers, one from the start and one from the end of the height vector. Compute the current area, move the smaller pointer to its direction, until two pointers meet.

The source code of O(n^2) method:
class Solution {
public:
    int maxArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxa = 0;
        if (height.size()<2){return maxa;}
        for (int i = 1; i<height.size();i++){
            for(int j = 0; j<i ; j++){
                int ar = abs(i-j)*min(height[i],height[j]);
                if (ar>maxa){ maxa = ar;}
            }
        }
        return maxa;
    }
};


The source code O(n):
class Solution {
public:
    int maxArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxa = 0;
        if (height.size()<2){return maxa;}
        int l = 0;
        int r = height.size()-1;
        
        while (l<r){
            int ar = abs(l-r)*min(height[l],height[r]);
            if (ar>maxa){ maxa = ar;}
            
            if(height[l]<=height[r]) { l = l+1;}
            else {r= r-1;}
        }
        
        
        return maxa;
    }
};

3 comments:

  1. How to prove the correctness of the algorithm after deriving it?

    ReplyDelete
  2. this solution is wrong please refer this link
    http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

    ReplyDelete
    Replies
    1. this will not work if the array is unsorted

      Delete