Container With Most Water: Why Greedy Two Pointers Works (Proof)

You're solving Container With Most Water (LeetCode #11). You read the solution:

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        
        # Move the shorter line
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

It works. But why?

Why do we move the shorter line? What if moving the taller line gives us a better answer? How do we know we're not missing the optimal solution?

This is the question that separates someone who memorizes from someone who understands. And in interviews, when asked "Why does this work?", you need a real answer.

This guide will give you both the intuitive explanation and the rigorous proof of why the greedy two pointers approach works for Container With Most Water.

TL;DR

• Intuition: Moving the taller line can never increase the area (width decreases, height stays limited by the shorter line)
• Proof: Moving the shorter line is the only way to potentially find a taller line that could increase area
• Key insight: Area is limited by the shorter line, so we must try to find a taller replacement for it
• Greedy choice: Always move the pointer at the shorter line
• Time complexity: O(n), visits each element once

The Problem Setup

Given: An array of heights representing vertical lines
Goal: Find two lines that form a container with the maximum water area

Area formula:

area = min(height[left], height[right]) * (right - left)
       ↑                                   ↑
   limited by shorter line            width between lines

Example:

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

Initial: left=0 (height=1), right=8 (height=7)
Area = min(1, 7) * (8 - 0) = 1 * 8 = 8

The Intuitive Explanation

Why Not Move the Taller Line?

Imagine you have two lines:

• Left line: height = 3
• Right line: height = 7
• Width: 10
• Current area: min(3, 7) × 10 = 3 × 10 = 30

What happens if we move the taller line (right)?

New state:

• Left line: height = 3 (same)
• Right line: height = ? (could be anything)
• Width: 9 (decreased by 1)
• New area: min(3, ?) × 9

Analysis:

• Width decreased from 10 to 9
• Height is still limited by the shorter line (left = 3)
• Even if the new right line is taller than 7, the area is still limited by 3
• Best case: min(3, ∞) × 9 = 3 × 9 = 27 < 30

Conclusion: Moving the taller line cannot increase the area.

Why Move the Shorter Line?

What happens if we move the shorter line (left)?

New state:

• Left line: height = ? (could be anything)
• Right line: height = 7 (same)
• Width: 9 (decreased by 1)
• New area: min(?, 7) × 9

Analysis:

• Width decreased from 10 to 9
• But if we find a taller left line (say, height = 6), the area could increase
• Example: min(6, 7) × 9 = 6 × 9 = 54 > 30

Conclusion: Moving the shorter line is the only way to potentially increase the area.

The Greedy Insight

Key observation: The area is always limited by the shorter line.

To increase the area, we must:

1. Find a taller replacement for the shorter line (to increase height)
2. Accept that width will decrease (inevitable as pointers converge)

Greedy choice: Always move the pointer at the shorter line, hoping to find a taller replacement.

The Rigorous Proof

Let's prove that this greedy approach finds the optimal solution.

Proof by Contradiction

Claim: The greedy algorithm (always move the shorter line) finds the maximum area.

Proof:

Suppose the optimal solution uses lines at positions i and j where i < j.

Case 1: Our algorithm considers the pair (i, j) at some point.

• Then we correctly compute its area and update max_area
• The optimal solution is found ✓

Case 2: Our algorithm never considers the pair (i, j).

This means at some point, we had pointers at positions left ≤ i and right ≥ j, but we moved one of them before reaching exactly (i, j).

Subcase 2a: We moved left past i (from some left < i to left > i).

This means when left < i and right ≥ j:

• We had height[left] < height[right] (we moved left)
• Therefore, height[left] < height[j]

The area at (left, j) is:

area(left, j) = min(height[left], height[j]) * (j - left)
              = height[left] * (j - left)  (since height[left] < height[j])

The area at (i, j) is:

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

Since left < i < j:

• Width at (left, j) is j - left (larger)
• Width at (i, j) is j - i (smaller)

For area(i, j) to be larger than area(left, j):

min(height[i], height[j]) * (j - i) > height[left] * (j - left)

But we know:

• height[left] < height[j]
• j - i < j - left

If height[i] ≤ height[left]:

area(i, j) = height[i] * (j - i) ≤ height[left] * (j - i) < height[left] * (j - left) = area(left, j)

If height[i] > height[left], we need:

height[i] * (j - i) > height[left] * (j - left)

But since we moved left (not right), we had height[left] < height[right]. The algorithm already considered (left, right) where right ≥ j, and that area was:

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

So we already found an area at least as good as area(left, j).

Subcase 2b: We moved right past j (symmetric argument).

Conclusion: In all cases, either we found the optimal pair (i, j), or we found an equally good or better pair. Therefore, the greedy algorithm is correct. ✓

Visual Proof

Let's trace through an example to see why it works:

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

Step 1: left=0 (h=1), right=8 (h=7)
        area = min(1,7) * 8 = 8
        Move left (shorter)
        
Step 2: left=1 (h=8), right=8 (h=7)
        area = min(8,7) * 7 = 49 ← NEW MAX
        Move right (shorter)
        
Step 3: left=1 (h=8), right=7 (h=3)
        area = min(8,3) * 6 = 18
        Move right (shorter)
        
Step 4: left=1 (h=8), right=6 (h=8)
        area = min(8,8) * 5 = 40
        Move either (same height)
        
... continue until left >= right

Maximum area found: 49

Why we didn't miss anything:

• When we moved left from 0 to 1, we knew that keeping left=0 with any right < 8 would give area ≤ 1 × width (limited by height[0]=1)
• When we moved right from 8 to 7, we knew that keeping right=8 with any left > 1 would give area ≤ 7 × width (limited by height[8]=7)

Why the Greedy Choice Is Safe

The Key Invariant

At each step, we maintain this invariant:

"We have not discarded any pair that could be optimal."

Why Moving the Shorter Line Is Safe

When we move the shorter line, we're saying:

"Any pair that includes this shorter line and a line closer to it cannot be better than what we've already seen."

Why?

• The width would be smaller
• The height is still limited by this shorter line
• Therefore, the area would be smaller

Why Moving the Taller Line Would Be Wrong

If we moved the taller line, we'd be saying:

"Any pair that includes this taller line and a line closer to it cannot be better."

But this is false!

• The width would be smaller (true)
• But the height might increase if we find a taller replacement for the shorter line
• The area could potentially increase

Implementation Details

The Complete Solution

def maxArea(height: List[int]) -> int:
    if len(height) < 2:
        return 0
    
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        # Calculate current area
        width = right - left
        current_height = min(height[left], height[right])
        area = width * current_height
        
        # Update maximum
        max_area = max(max_area, area)
        
        # Move the shorter line
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

JavaScript Version

function maxArea(height) {
    let left = 0, right = height.length - 1;
    let maxArea = 0;
    
    while (left < right) {
        const width = right - left;
        const currentHeight = Math.min(height[left], height[right]);
        const area = width * currentHeight;
        
        maxArea = Math.max(maxArea, area);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Java Version

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int width = right - left;
        int currentHeight = Math.min(height[left], height[right]);
        int area = width * currentHeight;
        
        maxArea = Math.max(maxArea, area);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Time and Space Complexity

Time Complexity: O(n)

• Each pointer moves at most n times
• We visit each element exactly once
• Constant work per iteration

Space Complexity: O(1)

• Only use a few variables (left, right, max_area)
• No extra data structures

Common Misconceptions

Misconception 1: "We might miss the optimal pair"

Reality: The proof shows we never discard a potentially optimal pair. We only discard pairs that are guaranteed to be suboptimal.

Misconception 2: "We should try all pairs to be sure"

Reality: Trying all pairs is O(n²). The greedy approach is O(n) and provably correct.

Misconception 3: "Moving the taller line might work sometimes"

Reality: Moving the taller line can never increase the area. The width decreases, and the height is still limited by the shorter line.

Misconception 4: "When heights are equal, it doesn't matter which to move"

Reality: When heights are equal, moving either pointer is fine. Both are "shorter" (or equally short), so the greedy choice applies to both.

Practice Strategy

To internalize this proof:

1. Solve Container With Most Water (#11) with the greedy approach
2. Manually trace a small example (5-6 elements) on paper
3. Prove to yourself why moving the taller line can't help
4. Explain the algorithm out loud as if teaching someone
5. Compare with brute force (O(n²)) to see the optimization

FAQ

Q: Why does this greedy approach work when greedy doesn't always work?

A: Greedy works here because we can prove that the greedy choice (move shorter line) never discards the optimal solution. This isn't true for all problems.

Q: What if both lines have the same height?

A: Move either one. Both are equally "short" in this case, so the greedy choice applies to both.

Q: Can I optimize further?

A: No. O(n) time and O(1) space is optimal. You must look at each element at least once to find the maximum.

Q: Why is width right - left and not right - left + 1?

A: We're measuring the distance between the lines, not counting elements in a window. If lines are at positions 0 and 3, the distance is 3.

Q: How do I remember this in an interview?

A: Remember: "Area is limited by the shorter line. To increase area, we must find a taller replacement for the shorter line. Moving the taller line can't help."

Conclusion

The Container With Most Water problem is a beautiful example of a greedy algorithm with a rigorous proof.

Key insights:

1. Area is limited by the shorter line (the bottleneck)
2. Moving the taller line can never increase area (width decreases, height stays limited)
3. Moving the shorter line is the only hope (might find a taller replacement)
4. Greedy choice is safe (never discards the optimal solution)

The algorithm:

while left < right:
    area = min(height[left], height[right]) * (right - left)
    max_area = max(max_area, area)
    
    if height[left] < height[right]:
        left += 1
    else:
        right -= 1

Why it works:

• We try the widest container first
• We systematically eliminate suboptimal pairs
• We never discard a potentially optimal pair
• We visit each element exactly once

Master this proof, and you'll not only solve the problem—you'll be able to explain why your solution is correct, which is what separates great engineers from good ones.

For more on two pointers, see the complete guide and opposite direction template.

Next time an interviewer asks "Why does this work?", you'll have a rigorous answer ready.