Container With Most Water: Two Pointers and the Proof

An array heights gives the heights of vertical walls standing at positions 0, 1, …, n − 1. Choose two walls; together with the ground they hold water up to the height of the shorter one. Return the largest amount of water two walls can hold, measured as min(heights[i], heights[j]) × (j − i).

Examples

Input	Output	Why
`heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]`	`49`	Walls 1 and 8 (heights 8 and 7): 7 × 7.
`heights = [1, 1]`	`1`	The only pair.
`heights = [4, 3, 2, 1, 4]`	`16`	The two outer walls, both 4, are 4 apart.

Constraints

2 ≤ n ≤ 10⁵
0 ≤ heights[i] ≤ 10⁴

Hints

Hint 1

Start with the widest pair, the two ends. Every other pair is narrower, so it only wins if it is taller.

Hint 2

Compare the two end walls. Could the shorter one be part of a better pair with any wall between them?

Hint 3

No: paired with anything nearer, the width shrinks and the height is still capped by that shorter wall. Discard it and move that pointer inward.

Dry run on `[1,8,6,2,5,4,8,3,7]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 9

Step 1 / 9

heights
10lo8162235445863778hi
area8best8
Walls 0 and 8: height min(1, 7) = 1, width 8, water 8 — a new best. Wall 0 is shorter, so no narrower pair using it can do better. Discard it.
Step 2 / 9

heights
1081lo62235445863778hi
area49best49
Walls 1 and 8: height min(8, 7) = 7, width 7, water 49 — a new best. Wall 8 is shorter, so no narrower pair using it can do better. Discard it.
Step 3 / 9

heights
1081lo622354458637hi78
area18best49
Walls 1 and 7: height min(8, 3) = 3, width 6, water 18. Wall 7 is shorter, so no narrower pair using it can do better. Discard it.
Step 4 / 9

heights
1081lo6223544586hi3778
area40best49
Walls 1 and 6: height min(8, 8) = 8, width 5, water 40. Wall 6 is no taller, so no narrower pair using it can do better. Discard it.
Step 5 / 9

heights
1081lo62235445hi863778
area16best49
Walls 1 and 5: height min(8, 4) = 4, width 4, water 16. Wall 5 is shorter, so no narrower pair using it can do better. Discard it.
Step 6 / 9

heights
1081lo622354hi45863778
area15best49
Walls 1 and 4: height min(8, 5) = 5, width 3, water 15. Wall 4 is shorter, so no narrower pair using it can do better. Discard it.
Step 7 / 9

heights
1081lo6223hi5445863778
area4best49
Walls 1 and 3: height min(8, 2) = 2, width 2, water 4. Wall 3 is shorter, so no narrower pair using it can do better. Discard it.
Step 8 / 9

heights
1081lo62hi235445863778
area6best49
Walls 1 and 2: height min(8, 6) = 6, width 1, water 6. Wall 2 is shorter, so no narrower pair using it can do better. Discard it.
Step 9 / 9

heights
108162235445863778
best49
The pointers have met. Every pair that could have beaten 49 was examined; the answer is 49.

How to think about it

Trying every pair is O(n²). The two-pointer version starts at the widest pair and argues, at each step, that one end can be thrown away for good.

Say heights[lo] ≤ heights[hi]. Any other pair using wall lo uses some wall k with lo < k < hi. That container is narrower than (lo, hi), and its height is at most heights[lo], which already caps (lo, hi). So it holds no more water. Wall lo has had its best chance; move lo right. The symmetric argument discards hi when it is the shorter.

Every step discards one wall, so the scan ends after n − 1 steps having examined every pair that could be optimal.

This is the same move as "pair with a given sum", but the input is not sorted. What makes two pointers work is not sortedness; it is having a comparison that rules out one end for ever.

Complexity. Time O(n) · Space O(1)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def most_water(heights):
    lo, hi = 0, len(heights) - 1
    best = 0
    while lo < hi:
        best = max(best, min(heights[lo], heights[hi]) * (hi - lo))
        if heights[lo] < heights[hi]:
            lo += 1        # the shorter wall caps every narrower pair it is in
        else:
            hi -= 1
    return best

#include <vector>
#include <algorithm>

int solve(const std::vector<int>& heights) {
    int lo = 0, hi = static_cast<int>(heights.size()) - 1, best = 0;
    while (lo < hi) {
        best = std::max(best, std::min(heights[lo], heights[hi]) * (hi - lo));
        if (heights[lo] < heights[hi]) ++lo;   // the shorter wall can never do better
        else --hi;
    }
    return best;
}

class Solution {
    public int mostWater(int[] heights) {
        int lo = 0, hi = heights.length - 1, best = 0;
        while (lo < hi) {
            best = Math.max(best, Math.min(heights[lo], heights[hi]) * (hi - lo));
            if (heights[lo] < heights[hi]) lo++;   // the shorter wall can never do better
            else hi--;
        }
        return best;
    }
}

function mostWater(heights) {
  let lo = 0, hi = heights.length - 1, best = 0;
  while (lo < hi) {
    best = Math.max(best, Math.min(heights[lo], heights[hi]) * (hi - lo));
    if (heights[lo] < heights[hi]) lo++;   // the shorter wall can never do better
    else hi--;
  }
  return best;
}

fn solve(heights: &[i64]) -> i64 {
    let (mut lo, mut hi) = (0usize, heights.len() - 1);
    let mut best = 0i64;
    while lo < hi {
        best = best.max(heights[lo].min(heights[hi]) * (hi - lo) as i64);
        if heights[lo] < heights[hi] {
            lo += 1;       // the shorter wall can never do better
        } else {
            hi -= 1;
        }
    }
    best
}

import Data.Array

solve :: [Int] -> Int
solve hs = go 0 (n - 1) 0
  where
    n   = length hs
    arr = listArray (0, n - 1) hs
    go lo hi best
      | lo >= hi  = best
      | l < r     = go (lo + 1) hi best'      -- the shorter wall can never do better
      | otherwise = go lo (hi - 1) best'
      where
        l = arr ! lo
        r = arr ! hi
        best' = max best (min l r * (hi - lo))

Where people lose marks

Moving the taller wall. The width shrinks and the height is still limited by the shorter wall, so it can only get worse; you may skip the optimum.
Measuring the height as the taller wall, or as the sum. Water spills over the shorter one.
Measuring the width as hi − lo + 1. The walls have no thickness here; the distance between positions 0 and 1 is 1.
Worrying about ties. When both walls are equal, moving either is safe, since neither can be in a better pair with anything between them.

Variants to try

Trapping rain water (the water held by all walls together, not one pair): also two pointers, carrying the highest wall seen from each side.
Return the pair of indices, not the area.
Skip ahead: after discarding the shorter wall, move past every wall that is no taller than it, since none of them can do better either.

Next problems

Easy10 min

Pair with a given sum in a sorted array

The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.

Open the problem → Medium20 min

All distinct triplets summing to zero

Sort, then fix one value and run the two-pointer scan on the rest. The whole difficulty is in the duplicates.

Open the problem →

Two walls holding the most water

Examples

Constraints

Hints

Dry run on `[1,8,6,2,5,4,8,3,7]`

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in a sorted array

All distinct triplets summing to zero

Keep going

Pair with a given sum in a sorted array

All distinct triplets summing to zero

The pattern behind it

Two walls holding the most water

Examples

Constraints

Hints

Dry run on [1,8,6,2,5,4,8,3,7]

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in a sorted array

All distinct triplets summing to zero

Keep going

Pair with a given sum in a sorted array

All distinct triplets summing to zero

The pattern behind it

Dry run on `[1,8,6,2,5,4,8,3,7]`