Problem 6.6 · Two PointersMedium

Container With Most Water

What it teaches: A greedy pointer rule with a proof: always move the shorter line, because the taller one can never do better with it.

Practise it on judges as “Container With Most Water”.

The problem

height[i] is the height of a vertical line at position i. Choose two lines that, with the x-axis, hold the most water. Return that amount: min(height[i], height[j]) × (j − i).

Example 1

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

Lines at 1 (height 8) and 8 (height 7): min 7 × width 7.

Example 2

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

Constraints

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

Pattern clues in the wording

→ Choose a pair maximising width × min height
→ n ≤ 10⁵ rules out all pairs

These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maxArea(int[] height) {
        int L = 0, R = height.length - 1, best = 0;
        return best;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	height = [1,8,6,2,5,4,8,3,7]	49
2	height = [1,1]	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Brute force: all pairs · O(n²)2. Optimal: move the shorter line · O(n)

Brute force: all pairs

Time O(n²) Space O(1)

Compute the area for every pair.

Approach 1

class Solution {
    public int maxArea(int[] height) {
        int best = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
        return best;
    }
}

Verdict: 5 × 10⁹ pairs at n = 10⁵: too slow.

Optimal: move the shorter line

Time O(n) Space O(1)

Start at both ends. The area is limited by the shorter line. Moving the taller line inwards keeps the same (or a shorter) limit while the width shrinks, so it can't help. Moving the shorter line is the only move that might find a taller limit. So always move the shorter one, and track the best area.

▶ Dry run: Always move the shorter sideheight = [1, 8, 6, 2, 5, 4, 8, 3, 7]

↑L

↑R

best(vars)

area = 8

Step 1/4min(1, 7) × 8 = 8. The left line (1) is shorter: move L.

Approach 2

class Solution {
    public int maxArea(int[] height) {
        int L = 0, R = height.length - 1, best = 0;
        while (L < R) {
            best = Math.max(best, Math.min(height[L], height[R]) * (R - L));
            if (height[L] < height[R]) L++;
            else R--;
        }
        return best;
    }
}

Verdict: Each step discards a line that can't be part of a better answer.

Before you submit

Edge cases and common mistakes

Test these inputs

Two lines
All equal heights
Zeros
Tallest lines at the ends

Mistakes people make

Moving the taller line.
Confusing this with Trapping Rain Water (which sums water over all bars).

Interview

Follow-up questions

Why is it safe to discard the shorter line?

Command Palette