Container With Most Water

Here two pointers are used to maximise instead of to hit a target, and the input is not sorted. That makes it the best test of whether you understand the pattern or only remember its trigger words. Interviewers almost always ask for the proof, so the argument matters as much as the code.

The problem

You are given a list of non-negative integers. Each value is the height of a vertical line standing at that position on the x-axis. Choose two lines; together with the x-axis they form a container. The water it holds is the shorter line's height times the distance between the lines. Return the most water any pair can hold.

• [3, 7, 5, 2, 8, 4, 6] → 30. The lines at positions 1 (height 7) and 6 (height 6) are 5 apart, and min(7, 6) × 5 = 30.
• [1, 1] → 1. The only pair: min(1, 1) × 1.

Constraints: 2 ≤ len(heights) ≤ 10⁵; 0 ≤ heights[i] ≤ 10⁴.

Clarifying questions

• Is the area limited by the shorter or the taller line? The shorter — water spills over it.
• Do lines between the two chosen ones get in the way? No, they are ignored. (If they did count, this would be the next lesson's problem, Trapping Rain Water.)
• Return the area or the positions? The area. Positions are an easy extension.
• Can heights be zero, and is the list sorted? Zero is allowed; the list is in no particular order. This matters: the usual two-pointer signal, sorted input, is missing. What makes the pattern apply here is a different kind of order — the width, which shrinks by exactly one every time a pointer moves.

Approach 1: the simple way

Measure every pair.

1def max_water_brute(heights: list[int]) -> int:2    """Measure every pair of lines."""3    best = 04    for i in range(len(heights)):5        for j in range(i + 1, len(heights)):6            best = max(best, min(heights[i], heights[j]) * (j - i))7    return best

Time O(n²), space O(1). At n = 10⁵ that is 5 × 10⁹ pairs. On our test machine 3,000 lines took about half a second in Python; 10⁵ lines would take several minutes.

The key insight

Start with the widest container: the first and last lines. Now you must give up one of them. Which one?

Suppose the left line is the shorter one, heights[left] < heights[right]. The current container holds heights[left] × (right − left). Every other container that uses the left line pairs it with some line between left and right. Such a container is narrower, and its height is still capped at heights[left] at most, whatever the partner. So every other container using the left line holds no more than the one you just measured. The left line has nothing left to offer — discard it.

Moving the taller line instead could only make things worse: the width shrinks, and the height stays capped by the same short line. Always move the shorter line. If the two are equal, the same argument applies to both, so moving either one is safe.

This is the same elimination as in Two Sum II: one comparison removes one line and every container it could still form.

Put numbers on it with the example. The first container uses position 0 (height 3) and position 6 (height 6): width 6, water 3 × 6 = 18. Every other container using position 0 is at most 5 wide and at most 3 tall, so it holds at most 15. None can beat 18, so position 0 is finished after a single measurement. Five candidate pairs are gone in one step. Note that the true answer (30) does not use the line we dropped — it never can, by this argument.

Approach 2: converging pointers, move the shorter side

1def max_water(heights: list[int]) -> int:2    """Largest amount of water two lines can hold."""3    left, right = 0, len(heights) - 14    best = 05    while left < right:6        width = right - left7        best = max(best, min(heights[left], heights[right]) * width)8        if heights[left] < heights[right]:9            left += 1                    # the short line caps every narrower pair10        else:11            right -= 112    return best

Dry run on [3, 7, 5, 2, 8, 4, 6]:

Six measurements instead of 21 pairs, and the answer 30 is found on the second one. The height-8 line at position 4 is the tallest, but it never makes the best container — width matters as much as height.

Complexity. Each round moves one pointer inward, so at most n − 1 rounds: O(n) time, O(1) space.

Edge cases

• Two lines. One measurement; the loop ends.
• Zero heights. A zero line holds nothing; the code measures 0 and moves on.
• Equal heights at both ends. The else branch moves right; by the argument above, moving either is safe.
• Strictly increasing heights. The left line is always shorter, so only left moves — still one pass.

We compared the two on 300 random lists of up to 10 heights between 0 and 10, which include many ties and zeros, and they agreed on every one. The same random test is how we found the short counterexample in the warning below.

Follow-ups

• "Return the two positions." Store left and right whenever best improves.
• "Prove it more formally." Show that the optimal pair is never discarded: when a line is dropped, every pair it could still form has been shown to be at most the area just recorded.
• "What if lines in between do block water?" Then you are summing water above every bar — Trapping Rain Water, the next lesson.