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 $i$-th line are $(i, 0)$ and $(i, \text{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

Solution

This problem is naturally amenable to the standard two-pointer solution, where we maintain a left and a right pointers, and move them towards each other - so as to maximize the area between the pointers.

Initially maxArea = 0, left = 0 and right = len(height) - 1.

We want to find the maximum value for maxArea. The current area is always min(height[left], height[right])*(right -left).

Question: Which pointer should be moved first? Left or right?

Since we are trying to maximize the area, we want to keep the larger of the two heights and move the pointer corresponding to the smaller height.

For example, in Example 1, initially, left = 0 and right = 8. So, maxArea = min(height[left], height[right])*(right -left) = min(1, 7)*8 = 8. For the next iteration, we will move the pointer corresponding to the smaller height, which, in this case, is left.

So, left = 1 now. So, we compute min(height[left], height[right])*(right -left) = min(8, 7)*7 = 49. Since 49 is greater than the previous maxArea, we update maxArea, so that maxArea = 49.

In this manner, we continue until the left and right pointers meet.

def maxArea(height):
    maxArea = 0
    left = 0
    right = len(height) - 1

    while left < right:
        maxArea = max(maxArea, (right - left) * min(height[left], height[right]))

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return maxArea

Runtime: Since the pointers left and right move towards each other, the number of iterations is $n$, so the runtime is $O(n)$. The only local variable being used is maxArea, so the space complexity is $O(1)$.

Back to Two Pointers Problems

---

anusha-murali.github.io