Container With Most Water

Asked in: Google, Facebook, Amazon, Adobe

Difficulty: Medium

Understanding the problem

Problem description

Given n non-negative integers a1 , a2 , …, an , where each represents a point at coordinate ( i , ai ). n vertical lines are drawn such that the two endpoints of line i is at ( i , ai ) and ( i , 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Problem Note: You may not slant the container and n is at least 2.

Example :

Input: [1,8,6,2,5,4,8,3,7]

Output: 49

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.

Basically, for each pair of heights, we have to maximize the product of width between them and a minimum of both the heights. It will be the maximum possible area. In the above case, we choose the pair 8 (at 1st index) and 7 (at 8th index). The width between them is the difference of their index, i.e. 7 and minimum of heights 8 and 7 is 7. So the area is 7*7 = 49.

You may now try to solve this problem from here .

Solutions

We will be discussing two approaches to solve this problem

Brute force solution —For each pair of heights we will compute the container with the most water.
Two pointers approach — Starting from two pointers at leftmost and rightmost indices we will gradually move to the inner line while discarding the smaller value between left and right.

1. Brute Force Solution

Brute force solution and the most straightforward approach to this problem is to calculate the area of water contained when selecting a pair of the heights from the input array. The maximum area of water will be obtained from the maximum of the areas formed by every pair of heights in the input array.

Solution steps

For every index i and j of the height input array, Calculate (j — i) * min(height[j],height[i]) and store it in a temporary variable
Update the result with the maximum of the result and calculated value.

Pseudo Code

int maxArea(int height[], int n)
{
    int maxarea = 0
    for(i = 0 to n-1)
    {
        for(j = i to n-1)
        {
            curr_area = (j - i)*min(height[j], height[i])
            maxarea = max(maxarea, curr_area)
        }
    }
    return maxarea
}

Complexity Analysis

Time Complexity: O(n²), Calculating area for all pairs of height So, n*(n-1)/2 operations.

Space Complexity: O(1) Constant extra space is used.

Critical Ideas to Think

Why are we considering every pair of heights?
For calculating area, why are we considering the minimum of height[i] and height[j]?
Can you think of a better approach?

2. Two Pointer approach

The intuition behind this approach is that the area formed between the lines will always be limited by the height of the shorter line. Further, Increasing the distance between the lines will increase the area.

Taking two pointers, one at the beginning and one at the end of the input height array and maintain a variable maxarea to store the maximum area obtained till now. At every step, we find out the area formed between the values at the two pointers, update maxarea and move the pointer pointing to the shorter line towards the other end by one step.

Why this approach works?
When we calculate the container size, the formula is (rightIndex - leftIndex) * min(height[leftIndex], height[rightIndex]).
So the key factor here is the width and height and the height is determined by a smaller height on the 2 indices.

But because we start from the leftmost line and rightmost line and gradually examining the inner lines, we notice that the width, (rightIndex - leftIndex) is monotonically decreasing as we examine more and more lines.

This means, once we pick some height in each step and calculate container size, that size is the maximum size of the container by using the same height as at that time the width is the maximum for that height. So there is no bigger container that appears for the same height we pick, so in each step, we pick min(height[leftIndex], height[rightIndex]) and once either of the height is used, we can forget about that index. So if the value at the left index is smaller then just increment left index else just decrement right index.

Solution steps

Use two pointers leftIndex and rightIndex initialized at 0 and n-1
Now compute the area implied by these pointers as (leftIndex-rightIndex)*min(height[leftIndex], height[rightIndex])
if height[leftIndex] < height[rightIndex]then, increment leftIndex by 1 else, decrement rightIndex by 1

Pseudo Code

int maxArea(int height[], int n)
{
    int maxarea = 0 
    // initialize two pointers on the both sides 
    int leftIndex = 0, 
    int rightIndex = n - 1
    while (leftIndex < rightIndex) 
    {
        int minHeight = min(height[leftIndex], height[rightIndex])
        maxarea = max(maxarea, (rightIndex - leftIndex)*minHeight)
        if(height[leftIndex] < height[rightIndex])
            leftIndex = leftIndex + 1
        else
            rightIndex = rightIndex - 1
    }
return maxarea
}

Complexity Analysis

Time Complexity — O(n) (Think!)

Space Complexity — O(1)

Critcal Ideas to Think

If height[leftIndex] < height[rightIndex]. Then is there any need to compare height[rightIndex-1] with height[leftIndex]? Why.
How we have maintained the maximum area. Try to visualize the steps using the above example.
What other problems could be solved using a similar approach?