Container With Most Water
Move the shorter wall inward — it's the only move that can help.
Two-Pointer Trace
Problem
Given an array of nonnegative heights, choose two different positions as the walls of a container. The container’s height is the shorter wall and its width is the distance between the positions; return the greatest area possible.
Examples
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Input: height = [1,1]
Output: 1
The Goal
Pick two walls. The water between them is as high as the shorter wall and as wide as the gap, so the area is min(height[left], height[right]) * (right - left). Find the biggest area.
For [1, 8, 6, 2, 5, 4, 8, 3, 7], the walls at indices 1 and 8 have heights 8 and 7. That's 7 × 7 = 49.
The shorter wall sets the level
Water can't rise above the shorter wall, however tall the other one is.
Every move is about the shorter wall.
Key Idea: Move the Shorter Wall
Start with the widest container, at the two ends. Every move inward makes it narrower.
Move the taller wall and the shorter one stays, still capping the height, so the area can only drop. The shorter wall has already met its widest partner and can't do better. Drop it, and look for a taller one.
With heights 8 and 7, move the 7.
Moving the taller wall keeps the same cap and loses width.
Heights 8 and 7: move the 7, not the 8.
The Algorithm
Measure, keep the best, then move the shorter wall in. Each step drops one wall for good.
while left < right:
best = max(best, min(height[left], height[right]) * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1When the walls are equal, move either one. Neither can do better with a narrower partner.
| Approach | Time | Why |
|---|---|---|
| Check every pair | O(n^2) | Too many containers |
| Move the taller wall | O(n) | Wrong: the shorter wall still caps the height |
| Move the shorter wall | O(n) | Each move safely drops one wall |
Walkthrough
Run it on [1, 8, 6, 2, 5, 4, 8, 3, 7].
The first container has walls 1 and 7, a gap of 8, and holds 8. The 1 is shorter, so left moves to the 8. Now min(8, 7) × 7 = 49, the best so far.
From there the right wall is never taller than 8, so right walks in. The areas are 18, 40, 16, 15, 4 and 6. None beats 49.
Checkpoint · predict the next step
Step 4 of 10 on the stage: min(8, 3) × 6 = 18, best 49. The right wall is shorter, and it can't do better with a narrower partner, so move right in.
left on 8 (index 1) · right on 3 (index 7) · area 18 · best 49
Pitfalls
- Moving the taller wall narrows the container and keeps the same cap.
- Use
min, notmax. Water spills over the shorter wall. - The width is
right - left, notright - left + 1. - Measure before you move, or you skip a container.
- With two walls, the answer is the shorter height. For
[1, 1], that's 1.
The walls have heights 4 and 9. Which pointer moves?
Complexity
Each step moves one pointer inward and neither turns back, so there are at most n - 1 moves: O(n) time. A few variables make O(1) extra space.
For 9 heights, that's 8 containers measured instead of all 36 pairs.
One pass, constant space
- Set up pointers and bestA few variables.O(1)
- Scan with two pointersEach pointer only moves inward.dominantO(n)
- Extra stateNo table, set or copy.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
One pass and constant memory.
In short
Two pointers at the ends bound the widest container. Area is limited by the shorter wall, so moving the taller one can never increase area; move the shorter pointer inward instead, tracking the max. One pass, no extra space.
Common mistake
Moving the taller line, or brute-forcing all O(n²) pairs instead of the greedy two-pointer shrink.