Skip to main content

Container With Most Water

Problem​

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.


Solution Approach​

Expected Time Complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] > height[r])
                r--;
            else
                l++;
        }
        return ans;
    }
};