Container With Most Water

The question

You are given a list of heights. Each is a vertical wall standing on the x-axis. Pick two walls so the water held between them is as much as possible. Water is width times the shorter wall, because it spills over the short one.

Explain it to a ten-year-old

You have a row of fence posts of different heights and a long plank. Rest the plank across two posts and pour water in. The water only rises as high as the shorter post, then spills. Start with the plank across the two posts at the far ends, the widest it can go. Now which post do you give up? The tall one is doing nothing, the short one is what stops the water. So move the short one in and try again. Keep going until the posts meet. You never need to try the other way.

The trick

This is the sorted Two Sum shape. Two pointers at the ends, one step inward per turn, done when they meet. The only thing that changed is the reason to move.

In Two Sum the list was sorted, so “too small, move lo” was obviously safe. Here nothing is sorted. The rule is move the shorter wall, and it is safe for a reason you must be able to say: the area is width times the shorter wall. If you keep the shorter wall and move the taller one, the width shrinks and the height is still capped by the same short wall, so every container you would try is worse. Moving the short wall is the only move that could possibly find a taller one. So you never skip the answer.

The steps

1. lo = 0, hi = len(h) - 1, best = 0.
2. While lo < hi:
   • area = (hi - lo) * min(h[lo], h[hi]). Keep the max.
   • If h[lo] < h[hi], lo += 1. Otherwise hi -= 1.
3. Return best.

def max_area(h):
    lo, hi = 0, len(h) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(h[lo], h[hi]))
        if h[lo] < h[hi]:
            lo += 1
        else:
            hi -= 1
    return best

Time O(n), each wall is given up at most once. Space O(1). The brute force tries every pair, n squared, and is what you say first.

The template

This is the Two Sum pointer template with one line changed. Memorise the shape once and this problem costs you nothing new.

lo, hi = 0, len(a) - 1
while lo < hi:
    MEASURE(a[lo], a[hi])          # Two Sum: the sum. Here: width × shorter wall
    if SHOULD_MOVE_LO:             # Two Sum: sum too small. Here: lo is the shorter wall
        lo += 1
    else:
        hi -= 1

What changes is written in capitals. MEASURE is what you compute at the two ends. SHOULD_MOVE_LO is the rule that decides which finger gives up. Everything else is the same code you already know.

The part to understand is what makes a move rule legal. The shape only works when the pointer you move can never have been part of a better answer with anything still inside. Sorted order gives you that in Two Sum. The “shorter wall caps the area” argument gives you it here. When a new problem hands you two pointers from the ends, your job is to find that sentence. If you cannot find it, the pattern does not apply and you should say so.

In GPU infrastructure

The move rule is the lesson. When a measure is the minimum of two sides, only the smaller side is worth touching. A ring all-reduce runs at the speed of its slowest link, so upgrading the fast NIC changes nothing. A pair of GPUs negotiate NVLink at the lower of their two link widths. A rack’s usable power is the smaller of the feed and the cooling. Every time you see min of two things, ask which side is the short wall before you spend money on the tall one.

What I am listening for

• Whether you say n squared first and then look for a way to throw pairs away without checking them. That is the whole idea of two pointers.
• Whether you move the shorter wall, and whether you can say why in one sentence. Moving the taller wall is the classic wrong answer, and I let it run until you notice.
• Whether you handle equal heights. Either pointer is fine, but you should know that and not freeze on it.
• Whether you connect it to Two Sum without me pointing it out. The same shape, a different move rule. Seeing that is the difference between knowing patterns and knowing problems.

Where it leads

• Two Sum II, sorted input. The same shape with the sorted-order move rule. Do it before this one.
• 3Sum. Fix one, run the pointer shape on the rest.
• Trapping Rain Water. The same walls, but now you count the water on top of every bar, not between two chosen ones. Two pointers from the ends again, tracking the tallest wall seen from each side. The hard cousin. Do it last.
• Valid Palindrome. The pointer shape where the move rule is “both, every time”.

Go deeper

• The problem statement: Container With Most Water on LeetCode, number 11.
• Container With Most Water on Hello Interview has the proof written out, and sits next to their two pointers overview.
• NeetCode’s walk-through draws the water and shows the wrong move first, which is the best way to remember the right one.
• The pattern page this belongs to: Two Sum, where the two-pointer template lives.

With AI on the table. The assistant writes this correctly and moves the shorter wall. I ask it to explain why, then I ask you whether its explanation is a proof or a hunch. Usually it says “the shorter wall limits the area” and stops. The missing half is “so every container that keeps it is no better”. I want you to notice the sentence is unfinished.