You are given a list called height. Each number is the height of a thin vertical wall standing at that position. Pick two walls. Together with the floor, they make a container that can hold water. Return the largest amount of water any pair of walls can hold.
The water held between the walls at positions l and r is:
\text{area} = \min(h[l],\, h[r]) \times (r - l)
Read it aloud as "the smaller of the two heights, times the distance between them". The distance r - l is the width of the container. The height is the shorter wall, because water spills over the lower side. In the first example, the walls at positions 1 and 8 have heights 8 and 7. The water height is 7, the width is 8 - 1 = 7, and the area is 7 \times 7 = 49.
There are up to 100,000 walls, and heights are zero or more.
There are about \frac{n^2}{2} pairs of walls, and we want the best pair without checking them all. So the real question is: which pairs can we prove are not worth checking?
def maxArea(height): best = 0 n = len(height) for l in range(n): for r in range(l + 1, n): best = max(best, min(height[l], height[r]) * (r - l)) return best
For 100,000 walls that is about five billion pairs. Far too slow.
The waste in one sentence: it measures many containers that are obviously smaller than one it has already measured.
Start with the widest container: one pointer l on the first wall and one pointer r on the last wall. Measure it.
Now one pointer must move inward. Whichever one moves, the container gets narrower, so the width always drops by 1. The only way to get more water is to find a taller height. So which pointer should move?
Move the shorter wall. Here is why that is safe.
Suppose the left wall is the shorter one. Think about every container that still uses this left wall, paired with any wall to its right but before r.
Each of those containers is narrower than the one we just measured, because the right wall is closer.
Each of them is no taller, because the water height can never exceed the left wall, and the left wall is already the limit.
Narrower and no taller means smaller. So none of those containers can beat the one we just measured. The short left wall has nothing more to offer. We can throw it away by moving l right.
If you moved the taller wall instead, the shorter wall would still be the limit on height, so you could not gain height, and you would lose width. That move can only make things worse.
Think of building a dog pen with two posts. One post is 2 feet tall and the other is 10 feet tall. The dog can jump over the 2-foot post, so the short post is the weak point. Moving the tall post closer cannot help, because the short post still decides how high the pen is. The only hope is to replace the short post and try a taller one.
This is the same "this item can never be part of a better answer, so drop it" argument from 4.5.2, applied to geometry instead of sums.
(1) Start at both ends. This is the widest possible container.
(2) best = 0. The most water found so far. No container can hold less than zero.
(3) Loop while the pointers have not met. A container needs two different walls.
(4) Measure, then remember the best.min(height[l], height[r]) is the water height. r - l is the width. Their product is the area. max keeps the larger of the old best and this area.
We measure before moving. If we moved first, we would never measure the widest container at all.
(5) The left wall is shorter, so drop it. Every remaining container that uses it is narrower and no taller, as argued above.
(6) Otherwise, drop the right wall. This branch runs when the right wall is shorter, and also when the two walls are equal. Is that safe in the equal case? Yes. With equal walls, every remaining container that uses either of them is narrower and still capped at that same height. So neither wall can do better, and dropping either one is fine.
Every turn moves exactly one pointer inward, so the gap between them always shrinks. That is why the loop always ends.
Take height = [1, 8, 6, 2, 5, 4, 8, 3, 7], positions 0 to 8.
l
r
Heights
Area
best
Move
0
8
1, 7
1 × 8 = 8
8
left shorter → l = 1
1
8
8, 7
7 × 7 = 49
49
right shorter → r = 7
1
7
8, 3
3 × 6 = 18
49
right shorter → r = 6
1
6
8, 8
8 × 5 = 40
49
equal → r = 5
1
5
8, 4
4 × 4 = 16
49
right shorter → r = 4
1
4
8, 5
5 × 3 = 15
49
right shorter → r = 3
1
3
8, 2
2 × 2 = 4
49
right shorter → r = 2
1
2
8, 6
6 × 1 = 6
49
right shorter → r = 1
The pointers meet and the loop ends. The answer is 49. It was found on the second step and never beaten. The first step is worth a second look. The wall of height 1 limited the widest container to an area of 8, so dropping it was clearly right.
Time. The pointers start n - 1 positions apart. Each turn moves one of them one step closer. So the loop runs at most n - 1 times. Each turn does a fixed amount of work: one min, one multiplication, one max and one comparison. So the time is O(n).
Space. Three numbers: l, r and best. The extra memory is O(1).
Two walls, the smallest input. The loop runs once, and the answer is the shorter height times 1.
Walls of height 0. The area is 0 for any container using them. The formula handles this with no special case.
Tall walls in the middle, such as [1, 100, 100, 1]. The first container has area 1 \times 3 = 3. Then the short end walls are dropped, and the two middle walls give 100 \times 1 = 100.
Two tempting rules are wrong: "move the pointer whose next wall is taller" and "always move the left pointer". Both give the right answer on small examples, so they feel correct.
The correct rule comes from the argument above, not from a guess about heights. If you cannot say why dropping a wall is safe, you do not have a two-pointer solution. You have a guess that happens to pass the examples.
Trapping Rain Water. It looks similar but is harder. Instead of one container, you measure the water sitting above every position. It uses the same idea, that the shorter side limits the water, in a different way. That is the next page, 4.5.5.
Largest Rectangle in Histogram. The bars are solid blocks, not thin walls, so a rectangle must fit under every bar it covers. That needs a different tool, the monotonic stack. See 4.8.7.
The general lesson: when the answer is limited by the smaller (or larger) of two ends, the limiting end is the one to drop.
"Prove that moving the shorter wall is correct." Give the full argument. Every container still using the shorter wall is narrower and no taller, so none of them can win.
"What if the two walls are equal?" Either move is fine. Every remaining container using either wall is narrower and capped at the same height.
"Why don't you sort the heights?" Because the positions are the widths. Sorting would move the walls and destroy the widths.
"What is the time complexity?"O(n), because each step moves one pointer inward and they meet after at most n - 1 steps.
One thing to volunteer: write down the area formula before any code, and point out that the height is the smaller wall. Half of all wrong answers 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 careful proof.