Free lesson · DSA Mastery - Interview Prep, End to End

Container With Most Water

Medium7 min readdsatwo-pointers

Container With Most Water

Container With Most Water is a classic two-pointer optimization problem with a genuinely clever insight. The brute force checks all O(n²) pairs of walls. The two-pointer solution achieves O(n) by realizing that the area is bounded by the shorter wall, so moving the taller wall inward can never help - only moving the shorter wall has a chance of improving the result.

The correctness argument here is more subtle than Two Sum II's, and it's worth understanding deeply. It's a frequent follow-up: "prove that moving the shorter wall is correct."

The Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that, together with the x-axis, form a container that holds the most water.

Return the maximum amount of water a container can store.

(You may not slant the container.)

Example 1:

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49

Explanation: The lines at index 1 (height 8) and index 8 (height 7)
             form a container of width 7 and height min(8, 7) = 7.
             Area = 7 * 7 = 49.

Example 2:

Input:  height = [1, 1]
Output: 1

Constraints:

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

Interactive animation: Width is right minus left, and the water stops at the shorter wall.

Approach

Interactive animation: Start with the widest container and always move the pointer at the shorter wall: eight checks for nine walls.

The area of a container formed by walls at indices left and right is:

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

The area is limited by the shorter of the two walls (water spills over the shorter one).

Two-pointer strategy: Start with the widest possible container (left = 0, right = n - 1). At each step:

Compute the current area; update the maximum.
Move the pointer at the shorter wall inward.

Why move the shorter wall? Because the area is width × min(heights). Moving either pointer reduces the width by 1. If we move the taller wall, the height is still bounded by the shorter wall (which didn't move), so the area can only stay the same or shrink. Moving the shorter wall is the only move that gives a chance of finding a taller bounding wall and thus a larger area.

graph TD
    A["left = 0, right = n - 1, max = 0"] --> B{"left < right?"}
    B -->|No| F["Return max"]
    B -->|Yes| C["area = (right - left) × min(h[left], h[right])"]
    C --> D["max = Math.max(max, area)"]
    D --> E{"h[left] < h[right]?"}
    E -->|Yes| G["left++ (move shorter wall)"]
    E -->|No| H["right-- (move shorter wall)"]
    G --> B
    H --> B
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This diagram shows the two-pointer approach. We start with the widest container, left at the start and right at the end. We compute the area, bounded by the shorter wall, and update the maximum. Then we move the pointer at the shorter wall inward, because that's the only move that could increase the bounding height.

The Correctness Argument (Why Moving the Shorter Wall Is Safe)

Interactive animation: Each check rules out a whole row or column of pairs, so the best container is never skipped.

Suppose height[left] < height[right]. Consider all containers that use left as the left wall: their area is (some width) × min(height[left], other wall). Since height[left] is the shorter wall and the width can only decrease as the right pointer moves inward, no container using left as the left wall can have a larger area than the current one (current width is the maximum possible for left, and the height is capped by height[left]).

So we can safely eliminate left - no future container needs it. We move left inward. By the same logic when height[right] is shorter, we eliminate right.

This elimination argument guarantees we never skip the optimal container.

Code Implementation

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

// Usage:
// System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));  // 49
// System.out.println(maxArea(new int[]{1, 1}));                       // 1

This Java code implements Container With Most Water. Left starts at the beginning, right at the end. We compute the area as width times the shorter wall's height, and track the maximum. We then move the pointer at the shorter wall inward, since that's the only move that could lead to a larger container.

When the two walls are equal in height, moving either pointer works - the code arbitrarily moves right (the else branch). Both choices are correct.

Walkthrough

Interactive animation: Step through both approaches on the lesson walls, every pair first and then the two pointers.

Trace on height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. n = 9.

left=0, right=8, max=0.

Iter 1: width=8, min(1, 7)=1. area=8. max=8.
  h[0]=1 < h[8]=7. left++ → left=1.

Iter 2: width=7, min(8, 7)=7. area=49. max=49.
  h[1]=8 < h[8]=7? No. right-- → right=7.

Iter 3: width=6, min(8, 3)=3. area=18. max=49.
  h[1]=8 < h[7]=3? No. right-- → right=6.

Iter 4: width=5, min(8, 8)=8. area=40. max=49.
  h[1]=8 < h[6]=8? No. right-- → right=5.

Iter 5: width=4, min(8, 4)=4. area=16. max=49.
  h[1]=8 < h[5]=4? No. right-- → right=4.

Iter 6: width=3, min(8, 5)=5. area=15. max=49.
  h[1]=8 < h[4]=5? No. right-- → right=3.

Iter 7: width=2, min(8, 2)=2. area=4. max=49.
  h[1]=8 < h[3]=2? No. right-- → right=2.

Iter 8: width=1, min(8, 6)=6. area=6. max=49.
  h[1]=8 < h[2]=6? No. right-- → right=1.

left=1, right=1. left < right? No. Loop exits.

Return 49.

Result: 49. The maximum container uses walls at indices 1 (height 8) and 8 (height 7), giving area 7 × 7 = 49.

Complexity Analysis

Aspect	Complexity	Notes
Time	O(n)	Each pointer moves inward at most n times
Space	O(1)	Two index variables

Why It Is O(n) Time

The two pointers start n - 1 apart and converge. Each iteration moves at least one pointer inward by one. Total iterations: at most n - 1. O(n).

Why It Beats Brute Force

Interactive animation: The same walls, the same answer: 36 area checks against 8.

Brute force checks all C(n, 2) ≈ n²/2 pairs - O(n²). For n = 10^5, that's ~5 × 10^9 operations (too slow). The two-pointer approach is ~10^5 - a massive improvement.

Variations & Follow-ups

What if you needed the indices of the optimal container, not just the area?

Track the best (left, right) alongside the max area. Update both when a new maximum is found.

What about Trapping Rain Water - isn't it similar?

Related but different. Container With Most Water finds the single best pair of walls. Trapping Rain Water (topic 10.10) computes the total water trapped across all positions, considering the terrain between walls. Trapping Rain Water also uses two pointers, but with a different invariant (tracking left-max and right-max).

What if the walls had thickness (occupied horizontal space)?

The width calculation would change to account for thickness. The two-pointer logic stays the same.

Why move the shorter wall and not always the left (or always the right)?

Always moving one side ignores the structure and could skip the optimum. Moving the shorter wall is the principled choice backed by the elimination argument.

What if all walls have the same height?

The maximum area is achieved at the widest container (the two ends). The pointers compute it on the first iteration and the area only shrinks afterward.

What about edge cases?

Two walls (n = 2): One container. Area = 1 × min(h[0], h[1]). Returns it.
All zeros: All areas are 0. Returns 0.
Monotonically increasing heights: The optimum often involves the last wall. The pointers explore correctly.
One very tall wall among short ones: The tall wall pairs with the best short wall it can reach. The algorithm finds it.
Equal-height walls at the ends: Either pointer can move; both choices give correct results.

Common Interview Pitfalls

Moving the taller wall. This can never increase the area (height is still bounded by the unmoved shorter wall, and width decreases). Always move the shorter wall.
Brute-forcing all pairs. O(n²) - too slow for large n. Use two pointers.
Forgetting that area is bounded by the shorter wall. min(height[left], height[right]), not the sum or the average.
Off-by-one in width. Width is right - left, not right - left + 1 (the walls are at the endpoints; water fills the gap between them).
Not being able to justify the greedy. Interviewers often ask "why is moving the shorter wall correct?" Be ready with the elimination argument.

Why This Problem Matters

Container With Most Water is the archetype of greedy two-pointer with an elimination argument. The insight - "the suboptimal side can be safely discarded" - is the heart of many converging-pointer proofs. The pattern appears in:

Trapping Rain Water (next-but-two topic) - bounded by the shorter side.
Largest Rectangle in Histogram (Section 16, with a stack) - related geometric optimization.
Two Sum II - eliminate one side based on the comparison.
Many "maximize/minimize over pairs" problems.

The deeper lesson: when a brute force checks all pairs, ask whether there's a property (sortedness, boundedness, monotonicity) that lets you prove one candidate is dominated and eliminate it without checking. That elimination is what turns O(n²) into O(n).

The next topic, 3Sum, combines sorting with two pointers to solve a problem that looks O(n³) but reduces to O(n²).

Back to DSA Mastery - Interview Prep, End to End