11. Container With Most Water

Problem #11 (Container With Most Water | Array, Greedy, Two Pointers)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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.

Example 1

Input:

height = [1,8,6,2,5,4,8,3,7]

Output:

49

Explanation:

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
In this case, the max area of water (blue section) the container can contain is 49.

Example 2

Input:

height = [1,1]

Output:

1

Constraints

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Solutions

Two Pointers(Proof by Formula)

We have an array of integers that represents heights. We have to pick two heights in which when filled water denotes the value of Area(A), where A represents the area the water takes up.

The idea is get two heights that can contain the largest amount of water.

A = width * height

width here represents the distance between the two heights(e.g. indices (1, 5) has a width of 4 since 5 - 1 = 4). height represents the minimum between two heights.

The main idea is the have two pointers that represents the indices of two heights(left and right heights), by default leftIndex = 0 and rightIndex = height.length - 1. And a variable maxArea that stores the largest area where water can be contained.

int maxArea = 0;
int leftIndex = 0, rightIndex = height.length - 1;

Next is to loop through the array of height while (leftIndex < rightIndex) holds true.

while(leftIndex < rightIndex){
    //  ...statements
}

The while loop is structured as such:

maxArea = max(maxArea, min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex));

• First is to assign the value of maxArea to which has the larger area, is it the current maxArea or the current Area of heights at indices (leftIndex, rightIndex).

if(height[leftIndex] < height[rightIndex])
    leftIndex++;
else
    rightIndex;

• Move the pointers, if the left height is less than the right height then we should move the left height to the its succeeding height, while, if greater than, move the right height to the preceded height.

Once, the while loop ends, maxArea should already be determined and can already be returned.

return maxArea

Code

• JAVA

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int leftIdx = 0, rightIdx = height.length-1;
        
        while(leftIdx < rightIdx){
            maxArea = Math.max(maxArea, Math.min(height[leftIdx], height[rightIdx]) * (rightIdx - leftIdx));
            if(height[leftIdx] < height[rightIdx])
                leftIdx++;
            else
                rightIdx--;
        }
        
        return maxArea;
    }
}

• C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int leftIdx = 0, rightIdx = height.size() - 1;
        
        while(leftIdx < rightIdx){
            maxArea = max(maxArea, min(height[leftIdx], height[rightIdx]) * (rightIdx - leftIdx));
            if(height[leftIdx] < height[rightIdx])
                leftIdx++;
            else
                rightIdx--;
        }
        
        return maxArea;
    }
};

Complexity

• Time: O(n)
• Space: O(1)