Container With Most Water#

Given an array where each value is the height of a vertical line drawn on the x-axis, pick two lines that, together with the axis, form a container holding the most water. The amount of water equals the shorter of the two heights times the horizontal distance between them. Return that maximum area.

Example#

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49, formed by the lines of height 8 and 7 that are 7 units apart.

Brute force#

Try every pair of lines, compute the area for each, and keep the maximum. This recomputes many pairs that cannot possibly be optimal.

• Time: O(n^2).
• Space: O(1).

Optimal approach#

Start with two pointers at the far ends, giving the widest possible container. The area is limited by the shorter line, so move the pointer at the shorter line inward. Moving the taller line could only shrink the width without any chance of a taller limiting side, while moving the shorter line gives a chance at a taller wall. Track the best area as the pointers converge.

Python solution#

 1def max_area(height):
 2    left, right = 0, len(height) - 1
 3    best = 0
 4    while left < right:
 5        width = right - left
 6        area = min(height[left], height[right]) * width
 7        best = max(best, area)
 8        if height[left] < height[right]:
 9            left += 1
10        else:
11            right -= 1
12    return best

Complexity#

• Time: O(n), each pointer moves inward at most n steps total.
• Space: O(1), only two indices and a running maximum.

This problem shows the greedy side of the two-pointer technique. Keep building with the 60-day challenge.