Container With Most Water: why you always move the shorter line

The move is obvious once someone tells you: put one pointer at each end, compute the area, slide the shorter line inward, repeat. Most explanations stop there. They show you the code, claim it is O(n), and move on as if the hard part were the implementation rather than the justification.

But the code is three lines. The hard part is convincing yourself — and being able to convince an interviewer — that you will never miss the optimal pair by making this greedy move. That is what this article is actually about.

The problem

You have an array height of n non-negative integers. Each integer represents a vertical line at that index. Pick two lines. Together with the x-axis they form a container. The amount of water the container holds is:

area = (right - left) * min(height[left], height[right])

The width is the distance between the two lines. The height is whichever of the two lines is shorter — because that is where the water spills over. Find the pair that maximises this area.

Example: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. The answer is 49, formed by the lines at index 1 (height 8) and index 8 (height 7): width is 7, height is min(8, 7) = 7, area is 49.

What the constraints force

n runs up to 10^5. That kills O(n²) immediately — 10^10 operations is a timeout by roughly four orders of magnitude. You need something linear or close to it.

Each height[i] is at most 10^4. So the maximum possible area is 10^5 * 10^4 = 10^9, which fits comfortably in a 32-bit integer. No overflow to worry about.

The minimum array length is 2, which means there is always at least one valid pair. No special empty-array handling needed.

These constraints point you toward O(n) time, O(1) space. That combination, for an array problem involving pairs, usually means two pointers.

Brute force: O(n²)

Before optimising, understand what you are optimising away. Every pair (i, j) where i < j is a candidate. There are n*(n-1)/2 of them. Check them all:

class Solution:
    def maxArea(self, height: list[int]) -> int:
        max_area = 0
        n = len(height)
        for i in range(n - 1):
            for j in range(i + 1, n):
                area = (j - i) * min(height[i], height[j])
                max_area = max(max_area, area)
        return max_area

public class Solution {
    public int MaxArea(int[] height) {
        int maxArea = 0;
        int n = height.Length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int area = (j - i) * Math.Min(height[i], height[j]);
                maxArea = Math.Max(maxArea, area);
            }
        }
        return maxArea;
    }
}

Correct. Straightforward. Too slow for n = 10^5, but worth reading because it makes the shape of the problem explicit. We are searching a two-dimensional space of pairs (i, j). The two-pointer approach collapses that into a single linear pass — the question is whether you can do that without skipping the optimal pair.

O(n²) time, O(1) space. With n at 10^5, you're looking at roughly 5 * 10^9 pair evaluations. That's too slow by a factor of about 50 on a typical OJ.

The greedy argument — this is the whole point

Place two pointers: left = 0, right = n - 1. That is the widest possible container. Record its area. Now you have to move one pointer inward — width will shrink regardless of which one you pick. The only variable you control is what happens to the height.

Say height[left] < height[right]. The current area is:

area = (right - left) * height[left]

because the left line is shorter and caps the water. Now consider what happens if you move the right pointer instead:

• Width decreases by 1: (right - left) becomes (right - left - 1).
• The new right boundary has some height height[right']. Even if it is taller than the current right, the area is still capped by height[left] — the short line did not move.
• So the new area is (right - left - 1) * min(height[left], height[right']), which is at most (right - left - 1) * height[left].

Smaller width, same cap, smaller or equal area. Every container you would form by moving the right pointer — with this particular left pointer — is strictly worse than or equal to what you just computed. You can discard all of them safely.

Moving the shorter line is the only rational choice. Not because it might find something better — it might not — but because moving the taller line is provably useless given the current shorter line.

The diagram below shows the two decisive steps on the canonical example:

Two pointers: O(n)

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            area = (right - left) * min(height[left], height[right])
            max_area = max(max_area, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

public class Solution {
    public int MaxArea(int[] height) {
        int left = 0, right = height.Length - 1;
        int maxArea = 0;
        while (left < right) {
            int area = (right - left) * Math.Min(height[left], height[right]);
            maxArea = Math.Max(maxArea, area);
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return maxArea;
    }
}

O(n) time, O(1) space. Each pointer moves inward at most n times total; the loop terminates when they meet.

The tie case — height[left] == height[right] — goes to the else branch and moves the right pointer. You could move either one. When both lines have the same height, the container's height is that value regardless of which pointer you advance, and the width is about to shrink by 1 either way. Neither choice skips the optimal answer: the only pair with this exact width and this exact height has already been recorded.

Tracing the example step by step

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

The maximum of 49 is never threatened after step 2. The right pointer marches all the way back because height[1] = 8 keeps dominating everything it meets, and none of the intervening lines are tall enough to compensate for the shrinking width.

Step 4 is worth pausing on. Both pointers land on height 8, the area is 40 — not 49. Width is 5, not 7. The tie-breaking else moves right, which is correct: that pair was already beaten at step 2 and cannot recover.

Completeness: why no pair is skipped

The argument above handles one move. But after many moves the claim is stronger: the two-pointer approach considers every pair that can possibly be optimal.

Proof by invariant. At each step, the set of pairs we have discarded are exactly those pairs where the shorter line is unchanged and the width is smaller. We proved those are all dominated by the current pair. Whatever pair (i*, j*) is optimal, neither pointer has passed it yet when the other pointer is still on the other side. When left = i* and right = j* — or vice versa — the area is computed and recorded. The loop cannot skip this configuration because the pointers converge one step at a time. The optimal pair is guaranteed to be evaluated.

Complexity

The two-pointer solution is asymptotically optimal for this problem. You cannot do better than O(n) — you need to look at every element at least once to establish that none of them form the optimal container.

Edge cases

n = 2 is the minimum. The loop runs exactly once, computes the only possible area, and returns it. No special handling needed — the constraints guarantee this works.

All elements equal — height = [5, 5, 5, 5]. The area starts at 5 * 3 = 15 with the full-width container. The right pointer moves inward on every step (tie case), and every subsequent area is smaller. The algorithm returns 5 * (n - 1), which is correct: the widest container wins when all heights are identical.

One element is zero — height = [0, 8, 3, 0]. Any container that includes a zero-height line contributes zero to the area. The algorithm handles this correctly: min(height[left], height[right]) will be zero when either boundary is zero, so those configurations simply do not win the max comparison. The zero-height pointer moves inward immediately on each encounter.

Two elements with one zero — height = [0, 0]. Both are zero, area is 0, loop runs once and returns 0. The else branch fires (tie), moves right to index 0, loop exits. Correct.

The common mistake is using max instead of min for the height. Water fills to the shorter line; above that it spills. Using max would give you an area larger than physically possible — it would fail the second example immediately (height = [1, 1] gives 1 with min, and 1 with max only because they're equal; try [1, 100] and you'll see max return 100 while the correct answer is 1).

Where this pattern fits in the two-pointer series

This problem comes after Two Sum II in the series, and it introduces something new: the greedy argument. Two Sum II's pointer movement is driven by a target sum — if the sum is too small you need a bigger value, so you move left up. Mechanical. Container With Most Water forces you to think harder: moving the shorter line is not obviously correct, and explaining why requires the discard argument above.

That discard argument — "every remaining pair reachable by this move is dominated" — is the mental model you carry forward. It appears again in Trapping Rain Water (42), Three Container problems, and any pair-search problem where one boundary limits the objective function.

Related problems

Trapping Rain Water (42) is the natural follow-up and it is harder in a specific way. Instead of choosing two boundary lines freely, you are computing how much water sits on top of every element given its neighbors. The two-pointer idea appears again — you still care about the shorter side — but now you accumulate water across all positions rather than just computing one rectangle. The greedy reasoning carries over, but the accounting is more involved. Solve Container With Most Water until the discard argument feels mechanical; then Trapping Rain Water will make sense rather than feel like a different problem category.

Two Sum II (167) uses the same left-right pointer convergence but for a sum target in a sorted array. If sum < target, move left up; if sum > target, move right down. The mechanical structure is identical; what changes is the condition that drives the decision. That problem is easier because the direction of the move follows from arithmetic.

3Sum (15) extends to triplets. You fix one element and run two pointers on the remainder. Understanding why two-pointer works on pairs is the prerequisite for understanding why the nested version works on triplets.

Valid Palindrome (125) is structurally similar — two pointers converging from both ends — but the termination condition and the comparison logic are different. Worth doing before 3Sum to build the muscle memory of pointer convergence without the added complexity of the greedy discard argument.