Container With Most Water — The Rain Barrel

Welcome back

Three bosses down. You've seen symmetric pointers (Boss 1), steered pointers on a sorted array (Boss 2), and composed pointers inside a loop (Boss 3).

Boss 4 is the one that taught a lot of people to actually trust this pattern. The move feels like cheating. You ignore tons of possibilities on purpose, and somehow you still find the best answer. Understanding why that works is the real prize here.

Today's boss: The Rain Barrel.

The story

You walk into a hardware store. The owner, Rina, is standing out back staring at a row of wooden posts nailed into the ground. They're all different heights.

"What's up?" you ask.

"I want to build a rain barrel," she says. "Pick two of these posts. I nail a flat board between them at the top of the shorter one. Water collects between them. I want the pair that holds the most water."

You squint at the posts.

heights: [1, 8, 6, 2, 5, 4, 8, 3, 7]
           0  1  2  3  4  5  6  7  8

You realize the amount of water each pair holds is:

water = min(left_height, right_height) * (right_index - left_index)

The width is the distance between the posts. The height is whichever post is shorter — water can't rise above the short one or it'd spill over.

You could try every pair. With 9 posts that's 36 comparisons. Fine. But Rina says she has a storage lot with 10,000 posts in it. That's 50 million pair checks. No good.

The problem, dressed up properly

Given n non-negative integers height[0..n-1], where each represents the height of a vertical line, find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water a container can store.

You cannot tilt the container. Fair warning — that assumption is load-bearing for the whole trick.

The naive way

def max_area(height):
    best = 0
    n = len(height)
    for i in range(n):
        for j in range(i + 1, n):
            area = min(height[i], height[j]) * (j - i)
            best = max(best, area)
    return best

Every pair. O(n²) time. With n = 10,000, that's 50 million iterations. Not great. Let's do better.

The move

Put a finger on the first post and a finger on the last post. Call the shorter post's height h and the distance between them w. Their area is h * w.

Now here's the question that unlocks everything: which finger should you move?

You have to move someone, because keeping them still doesn't get you anywhere. And whichever you move, the width shrinks by 1. So the only thing you can do to win is find taller posts.

• If you move the taller pointer inward, the height of the container is still capped by the shorter post. It was shorter before, and the shorter post didn't move. You gain no height, and you lose width. Strictly worse or equal.
• If you move the shorter pointer inward, you might find a taller post next, which could more than make up for the lost width. Strictly better is at least possible.

So: always move the shorter pointer. Ignore the taller side. Sounds crazy. It isn't.

Watching it work

Let's run it on [1, 8, 6, 2, 5, 4, 8, 3, 7].

Traced by hand:

heights: [1, 8, 6, 2, 5, 4, 8, 3, 7]

L=0 (1), R=8 (7) → min(1,7) * 8 = 8    → move L (L is shorter)
L=1 (8), R=8 (7) → min(8,7) * 7 = 49   → move R
L=1 (8), R=7 (3) → min(8,3) * 6 = 18   → move R
L=1 (8), R=6 (8) → min(8,8) * 5 = 40   → move either, say R
L=1 (8), R=5 (4) → min(8,4) * 4 = 16   → move R
L=1 (8), R=4 (5) → min(8,5) * 3 = 15   → move R
L=1 (8), R=3 (2) → min(8,2) * 2 = 4    → move R
L=1 (8), R=2 (6) → min(8,6) * 1 = 6    → move R
L=1 == R → stop

best = 49

Nine iterations. We checked 8 pairs out of 36 possible and still found the optimum. That's the win.

The code

def max_area(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    best = 0
 
    while left < right:
        h = min(height[left], height[right])
        w = right - left
        best = max(best, h * w)
 
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
 
    return best

Read it slow. There are three lines of work per iteration: compute the area, update the best, move the shorter pointer. That's it. The whole function is under ten lines.

Why is this correct?

This is the part beginners skip, and I want you to not skip it. The question is: how do we know we're not missing the best answer by ignoring all those pairs?

Claim: when we move the shorter pointer, we are throwing out pairs, but every pair we throw out is guaranteed to be worse than or equal to the one we just measured.

Proof sketch. Suppose height[L] < height[R]. We're about to move L. The pairs we're throwing out are (L, R-1), (L, R-2), ..., (L, L+1) — all the pairs where L is still the left pointer.

For any such pair (L, k) with k < R:

• The height of the container is min(height[L], height[k]), which is at most height[L].
• The width is k - L, which is at most R - L (strictly less, actually).
• So the area is at most height[L] * (R - L) — which is exactly the area we just computed.

Every pair we skip has an area no better than the one we already have. Safe to skip. We move on.

Why is this faster?

Each step moves either left or right by one, and the pointers never cross. Total steps: at most n - 1. Each step does O(1) work.

O(n) time, O(1) space.

For 10,000 posts, that's 50 million ops vs 10,000. 5,000x speedup.

Gotchas

1. Moving the taller pointer by accident. Read your if statement twice. If height[left] < height[right], you move left, not right. Flipping this gives wrong answers.

2. Ties. When height[left] == height[right], you can move either one. It doesn't matter. Both choices leave the same optimum reachable. Pick one and don't overthink it.

3. Off-by-one on width. The width is right - left, not right - left + 1. Think about it this way: if posts are at indices 0 and 8, the water spans the gap between them, which is 8 units wide.

4. Trying to prove correctness by induction on a specific example. It feels like magic because "skipping pairs" seems lossy. It isn't. Internalize the pair-comparison argument above, not the specific trace. The trace is a demo; the argument is the proof.

The pattern inside the pattern

Look at what just happened. You used two pointers, but not for symmetry (Boss 1), not for a target sum (Boss 2), not for an anchor plus a pair (Boss 3). You used them for a greedy elimination: at each step, you prove that one side of the decision is safe to discard, and you move on.

That's a new shape. Whenever you see a problem where the answer is bounded by two positions and moving one side can only ever make a specific quantity worse, two pointers with a greedy move is suddenly on the table.

Boss down. XP gained.

You cleared Boss 4. Rina has her rain barrel, and she owes you coffee.

What you walked away with:

• A two-pointer greedy move (always advance the bottleneck)
• A proof technique that makes the move feel obvious, not magic
• An O(n) replacement for O(n²) with only a few lines of code

Next up: Boss 5 — The Rooftop Puddles. The same city, now from above. Rain has fallen on a jagged skyline and you have to compute the total water trapped in the dips between buildings. This is the hardest boss in the dungeon. We'll build up to it slowly with a precompute trick first, then we'll refine it into a beautiful two-pointer version.

Bring an umbrella.