Container With Most Water: Two Pointer Greedy

LeetCode 11, Container With Most Water, is one of the cleanest examples of the two pointer greedy strategy. The brute force is obvious, the optimal solution is short, and the interesting part is proving why the greedy choice works. It also shows up constantly in interviews because it tests whether you actually understand the technique or just memorized the code.

Let's work through it from scratch.

The problem

You are given an array height of length n. Each element represents a vertical line drawn at position i with height height[i]. Find two lines that, together with the x-axis, form a container that holds the most water.

The area between lines at indices i and j is:

area = min(height[i], height[j]) * (j - i)

The shorter line is the bottleneck. Water cannot rise above it. And the distance between the lines is the width. You want to maximize the product of those two values.

Here is the classic example:

The optimal pair is indices 1 and 8, with heights 8 and 7. The water level is limited by the shorter line (7), and the width is 7 positions. That gives an area of 49.

Brute force: check every pair

The straightforward approach: try every pair of lines and track the maximum area.

def max_area_brute(height):
    n = len(height)
    best = 0

    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

This works, but it checks n*(n-1)/2 pairs. That is O(n^2). For an array of 100,000 elements, you are looking at billions of operations. Way too slow.

Two pointer greedy: O(n)

Here is the key insight: start with the widest possible container (pointers at both ends) and work inward. At each step, move the pointer that points to the shorter line.

Why? Because the area is limited by min(height[left], height[right]) * width. If you move the taller pointer inward, the width decreases and the height can only stay the same or get worse (it is still capped by the shorter side). The area is guaranteed to decrease or stay the same. So moving the taller pointer can never improve the result.

Moving the shorter pointer, on the other hand, might find a taller line that increases the height enough to compensate for the lost width. It is not guaranteed, but it is the only move that has any chance of improvement.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0

    while left < right:
        w = right - left
        h = min(height[left], height[right])
        best = max(best, h * w)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

One pass. Two pointers. One variable tracking the best. That is it.

Visual walkthrough

Let's trace the algorithm on [1, 8, 6, 2, 5, 4, 8, 3, 7]. L (orange) is the left pointer, R (green) is the right pointer.

Notice the pattern: the algorithm finds the optimal answer (49) on step 2 and then spends the remaining steps confirming that nothing beats it. Every step moves the shorter side inward, and the width keeps shrinking. The best area was found early because the widest container with two tall walls happened to be near the edges.

Why the greedy works (proof intuition)

This is the part that trips people up. Why is it safe to skip all the pairs we never check?

Think about it this way. When L and R are at positions 0 and 8, the area is min(1, 7) * 8 = 8. Now consider every pair that includes index 0 as the left wall: (0,7), (0,6), (0,5), and so on. The height of the left wall is always 1. The width only gets smaller. So every one of those pairs produces an area of at most 1 * 7 = 7, which is worse than our current best. We can safely eliminate all of them by moving L to the right.

This is the core invariant: when you move the shorter pointer, you are discarding pairs that provably cannot beat the current best. The shorter line acts as a ceiling on the area for every container that uses it. Since the width can only decrease as the pointers converge, no skipped pair can produce a larger area.

More formally: suppose height[left] <= height[right]. For any index r' between left+1 and right-1, the pair (left, r') has:

• Height at most height[left] (because min(height[left], height[r']) <= height[left])
• Width strictly less than right - left

So area(left, r') < height[left] * (right - left) <= area(left, right), which we already recorded. Every pair involving left with a narrower width is dominated. Moving left forward is safe.

Handling equal heights

When height[left] == height[right], does it matter which pointer you move? No. You can move either one. Here is why: if both heights are equal, then the current area is height[left] * (right - left). Moving either pointer inward reduces the width by 1. The new height is at most height[left] (since the other pointer still has the same height as a cap). So the area can only decrease or, at best, stay the same if the new line happens to be taller but is still capped. Moving either pointer is safe because the current pair is already recorded.

In the code above, the else branch handles both the "right is shorter" and "they are equal" cases by moving right left. Moving left right in the equal case would also be correct.

Complexity analysis

Time: O(n). Each step moves one pointer inward. The two pointers start at distance n-1 apart and converge. At most n-1 steps total.

Space: O(1). Three variables: left, right, best. No auxiliary data structures.

You cannot do better than O(n) time because you need to examine every element at least once. Any line you skip could be the tallest in the array.

The building blocks

Container With Most Water is built from one fundamental brick that appears across many LeetCode problems.

Opposite-end convergence

Two pointers start at the extremes and move inward based on a comparison. The decision rule is always the same shape: compare the values at both pointers, and move the one that limits your objective.

This same pattern powers:

• Two Sum II (move based on sum comparison with target)
• Trapping Rain Water (process the side with the smaller running max)
• Valid Palindrome (compare characters from both ends)
• 3Sum (inner loop uses converging pointers on sorted subarray)

The invariant is always: whichever pointer you move, you can prove the discarded pairs cannot improve the answer. You narrow the search space by one element per step, and you never backtrack.

Container With Most Water vs. Trapping Rain Water

These two problems are often confused because they both involve vertical bars and water. Here is the difference:

• Container With Most Water picks exactly two lines and asks how much water fits in the rectangle between them. The bars in the middle do not matter. You are maximizing a single area.
• Trapping Rain Water asks how much water is trapped above every bar, accounting for all the bars as terrain. The bars in the middle very much matter because water pools on top of them.

Both use converging two pointers, but the logic is different. In Container With Most Water, you move the shorter pointer because it caps the area. In Trapping Rain Water, you process the side with the smaller running max because that side's water level is fully determined.

If you can solve both from scratch and articulate the difference, you are in great shape for any two pointer interview question.

Reading about it is not enough

You have read the solution. You understand why the greedy choice is safe. But can you reproduce the proof intuition and write the code from scratch in three weeks?

Container With Most Water is deceptively simple. The code is five lines inside a while loop. But the reasoning is the part that slips away: why is it safe to skip pairs? Why move the shorter side? What happens when heights are equal? These are exactly the questions an interviewer will press on, and "I just memorized it" is not a satisfying answer.

The opposite-end convergence building block is small enough to drill on its own. Once it is in your long-term memory, assembling the full solution becomes mechanical. You are not memorizing a specific problem. You are internalizing a reusable technique.

Related posts

• Trapping Rain Water - The harder cousin that also uses converging two pointers, but with running maximums
• The Two Pointers Pattern - The foundation of the optimal solution, with converging pointer examples
• 3Sum - Another problem where opposite-end convergence is the inner loop