Container With Most Water and the Greedy Pointer Proof

If you interview at Google, Amazon, Bloomberg, expect some version of "Container With Most Water". It is rated Medium, and it falls squarely into the Two Pointers pattern — pattern-first preparation beats grinding random problems every time. Part 6 of 12 in the Two Pointers arc.

The Problem

You are given height, where height[i] is the height of a vertical line at position i. Choose two lines that, with the x-axis, form a container holding the most water. Return the maximum area. Width times the shorter height — and n can be 100,000, so the O(n²) pair scan is off the table.

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Lines at indices 1 and 8: min(8, 7) * (8 - 1) = 49.

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

Maximizing a function of a pair under a size constraint, where moving inward only shrinks width, is prime converging-pointer territory. The interview is really about the elimination argument — why moving the shorter line never discards the optimum.

The Approach

Start at both ends — maximum width — and record the area. The shorter line caps the area, and keeping it while shrinking width can only do worse: every container using the shorter line with any nearer partner is strictly smaller. So the shorter side is exhausted and its pointer moves inward.

That is a proof by elimination, not a heuristic. Being able to say why the greedy move is safe is the difference between a hire and a lean-hire on this question.

Python Solution

def max_area(height: list[int]) -> int:
    """Largest water area between any two lines."""
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        best = max(best, area)
        if height[left] < height[right]:
            left += 1   # left line exhausted: nothing better uses it
        else:
            right -= 1
    return best

Complexity

• Time: O(n) — one pointer moves inward per iteration
• Space: O(1) — constant state: two pointers and a running best

Interview Tips and Follow-Ups

• Rehearse the elimination proof in one breath — it is the single most-probed line of reasoning in this problem.
• On ties, moving either pointer is correct; say so instead of hedging.
• Do not confuse this with Trapping Rain Water (end of this arc) — different model, and naming the difference impresses.

If this clicked, continue the Two Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.