Medium

Container With Most Water

035

Given vertical line heights, return the maximum amount of water a pair of lines can contain.

EXAMPLES

Example 1

Input
{
  "height": [
    1,
    8,
    6,
    2,
    5,
    4,
    8,
    3,
    7
  ]
}

Output
49

FUNCTION SHAPE

height: intArray→int

SOLUTION NOTE

This is an example of using Two Pointers technique in a greedy fashion.

The idea is we want max_{i,j : i < j} (j-i) * (min(height[i], height[j]))

Basically out of all pairs of left,right edges, we want the maximum area rectangle of water that that rectangle can hold. Clearly we can brute force this formula in O(n^2) time, O(1) space.

However, this is wasteful. We can use a greedy, locally optimal algorithm to speed this up.

Since we want maximum area, it makes sense to start with the maximum width rectangle, being i = 0, j = n-1.

Imagine we have two edges, i,j. The lower height edge defines the amount of water the rectangle can hold. Since we can only shrink our window, (width) in order to increase the max area, we must abandon the lower height edge in search of a higher height. (ie. if we shrank the window by moving the higher height edge, all subsequent windows have max water area <= our current area, because the height of water is capped by the lower height edge.)

This is an amazing observation, because it saves a lot of redundant work. For example, if i = 0, j = n-1, and 0 is the lower height edge, we know that any rectangle with left edge i = 0 and j where j < n-1 will have less water area than the current area being (n-1 - 0) * (height[left]), because the first term the width will be strictly smaller, and the second term the minimum height will be less than or equal to height[left]. So basically, you can think of it as, on every iteration we save O(n) time. There will be O(n) iterations because we move each pointer exactly one every iteration, and we terminate once left crosses right, and both are initialized with space n apart.

This outlines a proof of the greedy stays ahead approach. We just showed that at every step, we can safely discard a set of solutions that will clearly be no better than our current. Which essentially means our greedy solution will not discard any optimal solution that exists, ie. is a smart brute force search. This is actually similar to the proof of correctness for the sliding window chapter.

This example outlines a common solution approach: model the problem mathematically, which instantly provides a brute force solution. However, you can leverage some greedy observations to make the solution optimally efficient.

Reveal reference solution +

pythonREFERENCE

# max_{i,j : i < j} (j-i) * (min(height[i], height[j]))
def maxArea(self, height: List[int]) -> int:
    res, left, right = 0, 0, len(height)-1
    while left < right:
        res = max(res, (right-left) * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return res

TimeO(n)

SpaceO(1)

Open on LeetCode ↗