W
← Blog/dsaarraystwo-pointers

Container With Most Water — Greedy Two-Pointer Proof [Google, Amazon, Meta]

Sanjeev SharmaSanjeev Sharma
15 min read

Advertisement

Problem Statement

Given n non-negative integers height where each value represents the height of a vertical bar at that index, find two bars that together with the x-axis form a container that holds the most water. Return the maximum amount of water a container can store.

Constraints: You may not slant the container. The water level is flat — determined by the shorter of the two bars.

Example:

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

Explanation: bars at index 1 (height 8) and index 8 (height 7) form a container of width 7 and effective height 7, giving area = 7 × 7 = 49.

Why This Problem Matters

Container With Most Water is a staple at Google, Amazon, and Meta for one reason: the brute force solution is obvious, but the optimal solution requires you to prove something non-trivial before you can trust it. Interviewers use this problem to separate candidates who can justify their algorithms from candidates who just pattern-match.

The brute force — check every pair of bars — is O(n²). Anyone can write that. The O(n) solution uses two pointers, but the critical interview moment is when the interviewer asks: "Why do you move that pointer and not the other one?" If you can answer that with a proof, you pass. If you say "I just know," you probably don't.

This problem also teaches a generalized technique called pointer elimination: at each step, you prove that an entire category of pairs cannot be optimal, so you skip all of them at once. This pattern repeats in problems like Trapping Rain Water, 3Sum, and others.

The difficulty is officially Medium, but the conceptual depth is closer to Hard. Get this one right and two-pointer problems across all difficulty levels become significantly easier.

The Core Formula

Before anything else, lock in this formula:

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

Let's break down each term:

min(height[left], height[right]) — The effective height of the container. Water cannot rise above the shorter bar. If the left bar is 3 and the right bar is 8, the water level is 3. The taller bar is irrelevant beyond determining that it doesn't limit the water.

(right - left) — The width of the container. This is simply the horizontal distance between the two chosen bars, measured in index units. Indices 1 and 8 give a width of 7.

Why min and not max? Because water spills over the shorter side. You could have a bar of height 100 on the right and a bar of height 1 on the left — you still only hold 1 unit of water per unit of width. The container is only as strong as its weakest side.

This formula is the entire engine of the problem. Every strategy decision flows from it.

Why Two Pointers — Starting at Maximum Width

The key insight is to think about what you're optimizing. You have two variables: height and width. You want to maximize their product (via min).

The smart starting point is maximum width: set left = 0 and right = n - 1. You cannot have a wider container than the one spanning the entire array. From there, you shrink inward — but every time you move a pointer, the width decreases by 1. That's a guaranteed loss. The only way to compensate is to find a taller bar. So as you shrink inward, you are always searching: "Can I trade a little width for significantly more height?"

This is the core trade-off. You start at the widest possible configuration and ask at each step: "Is there a better height available if I narrow the window?"

Two pointers give you a systematic way to explore this trade-off without checking every pair. The question is: which pointer do you move?

The Key Proof: Always Move the Shorter Pointer

This is the section that most explanations skip or state without justification. Here it is, carefully:

The claim: When height[left] < height[right], you should move left inward (increment it). When height[left] > height[right], move right inward (decrement it). When equal, it doesn't matter — move either.

Why is this safe? Why won't you miss the optimal pair?

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

current_area = height[left] × (right - left)

Now consider what happens if you instead move right inward to some position r' where left < r' < right. The area of the new pair (left, r') is:

new_area = min(height[left], height[r']) × (r' - left)

We know two things:

  1. (r' - left) < (right - left) — the width strictly decreased because r' < right
  2. min(height[left], height[r']) ≤ height[left] — the effective height is at most height[left], because height[left] is always the bottleneck (it's the shorter side)

Combining: new_area ≤ height[left] × (r' - left) < height[left] × (right - left) = current_area

Every pair (left, r') for any r' between left and right has area strictly less than current_area. There is no point evaluating any of them. You can discard all pairs that keep left fixed and move right inward. That means the pair (left, right) is already the best possible container involving left as the left boundary.

So you eliminate left entirely and move to left + 1. You haven't missed anything.

This is proof by elimination: rather than proving the algorithm finds the best pair, you prove that every pair you skip is guaranteed to be suboptimal. The algorithm is correct because the set of pairs you actually evaluate contains the optimal one, and every skipped pair is demonstrably worse than something already evaluated.

The symmetrical argument applies to moving right: when height[right] < height[left], the pair (l', right) for any l' between left and right has area ≤ height[right] × (l' - right), which is less than the current area. So right gets eliminated.

The equal-height case: When height[left] == height[right], both pointers bound the current area from above. You can move either one — the math works in both directions. Moving both simultaneously is also valid but unnecessary; the standard implementation just picks one (typically moves left).

The takeaway: Moving the shorter pointer gives you a chance of improvement — you might find a much taller bar next. Moving the taller pointer gives you no chance — the effective height is still capped by the shorter side, and width just got smaller. This isn't intuition; it's a provable guarantee.

Visual Dry Run

Let's trace the algorithm on height = [1, 8, 6, 2, 5, 4, 8, 3, 7] (indices 0–8, answer = 49).

Index:  0  1  2  3  4  5  6  7  8
Height: 1  8  6  2  5  4  8  3  7

Step 1: left=0, right=8

height[0]=1, height[8]=7
area = min(1,7) × (8-0) = 1 × 8 = 8
max_area = 8
Move left (shorter): left → 1

Step 2: left=1, right=8

height[1]=8, height[8]=7
area = min(8,7) × (8-1) = 7 × 7 = 49
max_area = 49
Move right (shorter): right → 7

Step 3: left=1, right=7

height[1]=8, height[7]=3
area = min(8,3) × (7-1) = 3 × 6 = 18
max_area = 49
Move right (shorter): right → 6

Step 4: left=1, right=6

height[1]=8, height[6]=8
area = min(8,8) × (6-1) = 8 × 5 = 40
max_area = 49
Equal height — move right: right → 5

Step 5: left=1, right=5

height[1]=8, height[5]=4
area = min(8,4) × (5-1) = 4 × 4 = 16
max_area = 49
Move right (shorter): right → 4

Step 6: left=1, right=4

height[1]=8, height[4]=5
area = min(8,5) × (4-1) = 5 × 3 = 15
max_area = 49
Move right (shorter): right → 3

Step 7: left=1, right=3

height[1]=8, height[3]=2
area = min(8,2) × (3-1) = 2 × 2 = 4
max_area = 49
Move right (shorter): right → 2

Step 8: left=1, right=2

height[1]=8, height[2]=6
area = min(8,6) × (2-1) = 6 × 1 = 6
max_area = 49
Move right (shorter): right → 1
left == right → STOP

Result: 49 — found at Step 2 with bars at index 1 (height 8) and index 8 (height 7).

Notice how the algorithm ran 8 steps for 9 elements, which is always exactly n - 1 steps. Each step moves one pointer inward, so in n - 1 steps the pointers meet. That's O(n).

ASCII Visualization

Height array: [1, 8, 6, 2, 5, 4, 8, 3, 7]

       |           |
       |           |       |
       |   |       |       |
       |   |   |   |       |
       |   |   |   |   |   |
       |   |   |   |   |   |   |
   |   |   |   |   |   |   |   |
---+---+---+---+---+---+---+---+---
   0   1   2   3   4   5   6   7   8

       ^                           ^
      left                       right

Water fills between index 1 and index 8:
min(8, 7) = 7 height × 7 width = 49 units

Common Mistakes

Mistake 1: Moving the wrong pointer. Moving the taller pointer when heights are unequal is the classic mistake. If height[left]=3 and height[right]=9, moving right inward reduces width while the height stays capped at 3. Area can only decrease or stay the same. There is nothing to gain. Always move the pointer at the shorter bar.

Mistake 2: Off-by-one on initialization. Setting right = n instead of right = n - 1 causes an out-of-bounds access on the first area calculation. The pointers should start at valid indices: left = 0, right = len(height) - 1.

Mistake 3: Skipping the area calculation before moving the pointer. A common bug is moving the pointer first and computing area after, which means you never evaluate the starting configuration (0, n-1). Always compute area before advancing pointers.

Mistake 4: The brute force trap in an interview. Writing O(n²) first is fine — but staying there is not. If you present a nested loop solution and stop, most FAANG interviewers will probe for the O(n) approach. The expected progression is: state brute force, identify its inefficiency, derive the two-pointer approach with proof, implement, analyze complexity. Practicing this progression matters as much as knowing the answer.

Mistake 5: Confusing this problem with Trapping Rain Water. Both problems involve arrays of heights and water. But they ask completely different questions (see the Follow-up section). Mixing up the water calculation formula — or trying to sum water at every index — gives wrong answers here.

Solutions

Brute Force — O(n²) Time, O(1) Space

Useful to state in an interview to anchor the discussion, but never submit as a final answer.

Python:

def maxArea(height: list[int]) -> int:
    max_water = 0
    n = len(height)
    # Check every pair of bars — O(n²)
    for i in range(n):
        for j in range(i + 1, n):
            # Water height = shorter bar; width = distance between bars
            area = min(height[i], height[j]) * (j - i)
            max_water = max(max_water, area)
    return max_water

JavaScript:

function maxArea(height) {
    let maxWater = 0;
    const n = height.length;
    // Check every pair — O(n²), too slow for large inputs
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const area = Math.min(height[i], height[j]) * (j - i);
            maxWater = Math.max(maxWater, area);
        }
    }
    return maxWater;
}

Optimal Two-Pointer — O(n) Time, O(1) Space

Python:

def maxArea(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        # Compute area for current pair of bars
        h = min(height[left], height[right])
        width = right - left
        area = h * width
        max_water = max(max_water, area)

        # Move the pointer at the shorter bar inward.
        # Proof: keeping the shorter bar and moving the taller one
        # can only decrease or maintain area (width drops, height
        # is still capped by the shorter side). So we eliminate
        # the shorter bar from consideration and advance past it.
        if height[left] < height[right]:
            left += 1
        elif height[right] < height[left]:
            right -= 1
        else:
            # Heights are equal — moving either pointer is safe.
            # Both are symmetric bottlenecks.
            left += 1

    return max_water

JavaScript:

function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxWater = 0;

    while (left < right) {
        // Area = shorter bar height × distance between bars
        const h = Math.min(height[left], height[right]);
        const width = right - left;
        const area = h * width;
        maxWater = Math.max(maxWater, area);

        // Always move the pointer at the shorter bar.
        // Moving the taller pointer cannot improve area —
        // the shorter side is still the bottleneck and width just shrunk.
        if (height[left] < height[right]) {
            left++;
        } else if (height[right] < height[left]) {
            right--;
        } else {
            // Equal heights: moving either is valid
            left++;
        }
    }

    return maxWater;
}

Complexity Analysis

ApproachTimeSpaceNotes
Brute ForceO(n²)O(1)Check all n(n-1)/2 pairs
Two PointersO(n)O(1)Each pointer moves at most n-1 steps total

Time — O(n): In each iteration, one of the two pointers moves inward by one position. The pointers start at distance n - 1 apart and meet when they are at the same index. That means exactly n - 1 iterations occur regardless of the input. Each iteration does O(1) work (two array accesses, one comparison, two arithmetic operations). Total: O(n).

Space — O(1): No additional data structures. Only left, right, max_water, and temporary variables for the current area calculation. Memory usage is completely independent of input size.

Follow-up Questions

How does this relate to Trapping Rain Water (LC 42)?

Both problems share the same setup — an array of bar heights — but they ask fundamentally different questions.

Container With Most Water (LC 11): You pick exactly two bars and ask how much water they can hold between them as a container. The answer is min(height[left], height[right]) × (right - left). You maximize this over all pairs.

Trapping Rain Water (LC 42): You ask how much total water gets trapped across the entire landscape after rainfall. Water at each position i is trapped up to min(maxLeft[i], maxRight[i]) - height[i], where maxLeft and maxRight are the tallest bars to the left and right of i. You sum this over all positions.

The core difference: LC 11 cares about the best single container formed by two outer walls. LC 42 cares about every position's trapped water summed together — the bars in between matter because they form the floor of smaller sub-containers. In LC 11, the bars in between are irrelevant; only the two selected endpoints matter.

Both can be solved with two pointers and both involve min of two heights, which is why they're often studied together. But the formulas and what you're summing are completely different. If you find yourself trying to sum water at every index in LC 11, you've slipped into LC 42 thinking.

What about Largest Rectangle in Histogram (LC 84)?

Another classic problem with a structural similarity: you have an array of heights and want to find the maximum rectangular area. But instead of water between two bars, you're looking for the largest rectangle that fits inside the bars. This requires a monotonic stack — a different pattern entirely. The shared DNA is that both problems reason about "what limits this rectangle/container," which in both cases is the minimum height within some range.

This Pattern Solves

The pointer elimination technique used here appears throughout two-pointer problems:

  • 3Sum (LC 15): Fix one element, then use two pointers on the remainder. At each step, eliminate the left or right pointer based on whether the current sum is too small or too large.
  • Two Sum II — Sorted Array (LC 167): Identical elimination logic — if the current sum is too small, advance left; if too large, move right.
  • Minimum Size Subarray Sum (LC 209): Shrink from one end when a condition is met.
  • Squares of a Sorted Array (LC 977): Place the largest square at the end by comparing absolute values from two ends.

In all these cases, the key is proving that you can safely skip an entire class of candidates because they cannot beat what you've already seen or will see. Pointer elimination is the formal name for this class of greedy argument.

Key Takeaway

Container With Most Water is a proof problem disguised as a coding problem. The code is five lines; the insight is that moving the shorter pointer is the only safe choice because moving the taller pointer mathematically cannot improve the area — the effective height is already capped by the shorter side, and width only decreases. Once you internalize that proof, you stop memorizing the algorithm and start understanding why it works, which transfers to every two-pointer problem you encounter afterward.

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro

twitterlinkedingithubmail

← Previous

Product of Array Except Self — The Prefix × Suffix Trick That Google Loves

Next →

3Sum — The Deduplication Problem Every FAANG Interviewer Loves [LC 15]