4.5.4 — Container With Most Water

LeetCode 11 · Medium · ★ Blind 75

The problem

Each number is the height of a vertical line. Pick two lines so that the container they form holds the most water.

height = [1,8,6,2,5,4,8,3,7]   →  49

The area between lines at l and r is:

\text{area} = \min(h[l],\, h[r]) \times (r - l)

The width is how far apart they are. The height is the shorter of the two walls, because water spills over the lower one.

Up to 100,000 lines, so O(n^2) is out.

The pattern

Start with the widest possible container: one pointer at each end. That gives the maximum width, so any improvement has to come from height.

Now the decision. Which pointer moves?

Move the shorter wall inwards. Here is why that is safe.

The width shrinks on every move, no matter which pointer you move. That loss is unavoidable. So the only question is whether the height can grow enough to make up for it.

If you move the taller wall inwards, the height is still capped by the shorter wall, which has not changed. So the height cannot increase, and the width has decreased. Every container you could reach that way is smaller. Nothing is lost by never trying them.

If you move the shorter wall, you at least have a chance of finding a taller one.

So the shorter wall is a bottleneck that can never be part of a bigger container than the one you just measured. Discard it. That is the same discard proof as 4.5.2, applied to geometry instead of sums.

The solution

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0

        while l < r:
            best = max(best, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return best

TypeScript

function maxArea(height: number[]): number {
  let l = 0, r = height.length - 1, best = 0;

  while (l < r) {
    best = Math.max(best, Math.min(height[l], height[r]) * (r - l));
    if (height[l] < height[r]) l++;
    else r--;
  }

  return best;
}

Measure first, then move. Measuring after moving would skip the widest container entirely.

When the two walls are equal, either move works, and the else branch handles it by moving r. It cannot cost you the answer: with equal heights, moving either one leaves the height capped at that same value, so both remaining containers are narrower and no taller. You could move both at once and save one iteration.

The l < r condition is what prevents an infinite loop. Every iteration moves exactly one pointer inwards, so the gap always shrinks and the loop always ends.

Trace

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

l	r	heights	area	move
0	8	1, 7	1 × 8 = 8	left is shorter → l++
1	8	8, 7	7 × 7 = 49	right is shorter → r--
1	7	8, 3	3 × 6 = 18	r--
1	6	8, 8	8 × 5 = 40	equal → r--
1	5	8, 4	4 × 4 = 16	r--

and so on downwards. The answer 49 was found on the second step and never beaten.

Complexity

O(n) time — the pointers move towards each other and cover the array once. O(1) space.

The mistake worth naming

The tempting wrong rule is move whichever pointer will give the taller next wall, or always move the left one. Both are wrong, and both pass small test cases.

The correct rule comes from the argument above, not from intuition about heights. If you cannot state why discarding an element is safe, you do not have a two-pointer solution — you have a guess that happens to pass.

Where this goes next

• Trapping Rain Water — looks similar and is genuinely harder, because you measure the water above each individual position rather than one container. It is 4.5.5 and it uses the same "the shorter side is the bottleneck" insight in a different way.
• Largest Rectangle in Histogram — bars are solid rather than thin lines, so the answer needs a monotonic stack instead. 4.8.

The rule: when the answer is capped by a minimum or a maximum of two ends, the limiting end is the one to discard.

What the interviewer will push on

"Prove that moving the shorter line is correct." The full argument above: width always shrinks, and moving the taller line cannot raise the height, so those containers are all strictly worse.

"What if the two heights are equal?" Either move is fine, for the reason given above.

"Why does this not need sorting?" Because the rule comes from geometry, not from order. Sorting would destroy the positions, and the positions are the width.

One thing to volunteer: state the area formula before writing any code, and point out that the height is the min. Half of all wrong solutions to this problem come from using the wrong height.

Next: 4.5.5 Trapping Rain Water — the hardest problem in this group, and the one where the two-pointer version needs a real proof.