Container With Most Water (LeetCode 11)

The problem

You get an array height where height[i] is the height of a vertical wall at position i. Choose two walls; together with the x-axis they form a container. The water it holds is (distance between walls) × (height of the shorter wall). Return the largest amount any pair can hold.

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49

The walls at index 1 (height 8) and index 8 (height 7) are 7 apart, and the shorter one is 7 tall: 7 × 7 = 49.

How to think about it

Start with brute force. Try every pair (i, j) and compute the area: O(n²). It works, but for 10⁵ walls that’s 5 billion pairs.

Start wide. The widest container uses the two outermost walls. Any other container is narrower, so to beat it, it has to be taller. That suggests starting with i = 0, j = n - 1 and moving inward, looking for height to make up for lost width.

The key insight: always move the shorter wall. The area is capped by the shorter wall. Say height[i] < height[j]. If you kept i and moved j inward, the width shrinks and the height can never go above height[i], so every container that uses wall i with a closer partner is no better than the one you just measured. Wall i has nothing left to offer, so drop it with i += 1. Each step throws out one wall, safely.

Which pattern is this? Converging two pointers with a greedy elimination argument. The tell is “choose a pair, the score depends on the distance and the smaller of the two values”.

Approach

1. Set i = 0, j = n - 1, best = 0.
2. While i < j, compute (j - i) * min(height[i], height[j]) and update best.
3. Move the pointer at the shorter wall inward. On a tie, moving either one is fine.
4. Return best.

Solution

def max_area(h):
    i, j, best = 0, len(h) - 1, 0
    while i < j:
        best = max(best, (j - i) * min(h[i], h[j]))   # width × shorter wall
        if h[i] < h[j]: i += 1                         # shorter wall can't do better
        else: j -= 1
    return best
# max_area([1,8,6,2,5,4,8,3,7]) -> 49

Dry run

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

(Steps at j = 4 and j = 3 give 15 and 4.) The answer is 49.

Complexity

• Time: O(n). Each iteration moves one pointer inward, so there are n − 1 iterations.
• Space: O(1). Two indices and a running maximum.

Edge cases and pitfalls

• Two walls: one iteration, and the answer is min(h[0], h[1]).
• Zero-height walls give area 0; they’re dropped immediately.
• Moving the taller wall is the classic wrong instinct. It can only keep or reduce the cap, while the width definitely shrinks.
• Confusing it with Trapping Rain Water. Here you pick just two walls and the walls between them don’t matter. In Trapping Rain Water every bar holds water.
• Using max(h[i], h[j]) for the height is wrong: water spills over the shorter wall.

Related problems

• Trapping Rain Water (LeetCode 42): the same “the shorter side decides” idea, applied to every bar.
• Two Sum II – Input Array Is Sorted (LeetCode 167): another converging scan where each move rules out one element.
• Largest Rectangle in Histogram (LeetCode 84): area limited by the shortest bar, solved with a monotonic stack.