Container With Most Water
How to find the two walls that trap the most water between them, checking a handful of pairs instead of every pair.
The job
You have a row of vertical walls, each with a height. Pick two of them to trap water between — the amount held is the distance between them times whichever wall is shorter. Maximize that.
The obvious way
Try every pair of walls, compute the trapped water for each, and keep the largest.For 9 walls that is on the order of 36 pairs.
The idea
Start as wide as possible — the two outer walls — then always move the SHORTER of the two inward. Moving the taller one can only shrink the width while the height stays capped by the shorter wall, so it could never produce a bigger answer. Every move is provably safe to make.
Think of it like this. Two people holding the ends of a tarp between them, trying to catch as much rain as possible. The tarp's capacity is set by whoever is holding their end lower — so the taller holder has no reason to step inward, and it is always the shorter one who moves.
Maximizing width × the shorter wall
9 walls, each a height. Pick two of them so the water trapped between — width times the SHORTER wall — is as large as possible.
def max_area(height):
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
else:
right -= 1
return bestThis run
Best container is walls 1 and 8, holding 49 — found by checking 8 pairs instead of every possible pair.
The names you just watched
left and right
The two candidate walls. They only ever move inward, never back out, so the gap between them shrinks by exactly one on every check.
The shorter one always moves
Not "whichever seems better" — provably the shorter wall, every time. The taller wall can never be part of a bigger answer while the shorter one stays put.
Width only ever shrinks
Since width is strictly decreasing, the only way a later pair can beat an earlier one is with a taller limiting wall — which is exactly what moving the shorter wall searches for.
How to spot this shape
The tell: The answer is width times a value capped by the smaller of two endpoints, and you can prove that moving the larger endpoint inward never helps.
Reach for it when
- The objective multiplies a distance (width) by a minimum of two values.
- A brute-force answer checks every pair of positions.
- You can argue "moving X could only make things worse" for one of the two ends.
- The array represents physical heights, walls, or capacities read left to right.
Not this when
- The objective is a SUM across the range, not a min-times-width — that usually wants prefix sums or Kadane-style scanning instead.
- Both ends could plausibly need to move in the same step — the one-sided proof breaks.
- The best answer needs three or more chosen positions, not two.
- There is no monotone "safely discard" argument for either end.
Practice
6 problemsThe lesson, exactly. Moving the taller wall inward can never help — that is the whole proof behind always moving the shorter one.
A close cousin, not the same problem: every bar traps water up to min(max-so-far-left, max-so-far-right), summed across all of them, not just the two outer walls.
Fix one value, then run a converging two-pointer sweep on the rest — the same inward walk, different payoff being optimized.
Same fixed-value-plus-converging-pair structure as 3Sum, but track the smallest absolute distance to the target instead of an exact match.
A different technique (monotonic stack), but the same "width × the limiting height" objective as this lesson’s area formula.
The 2D generalization of Trapping Rain Water — a priority queue expanding inward from the border replaces the two converging walls.