Container With Most Water - Java Solution

Problem

height[i] is the height of a vertical wall standing at x-position i. Pick two walls; together with the x-axis they form a container whose water level is limited by the shorter wall. Return the largest amount of water any pair can hold, i.e. max of min(h[i], h[j]) × (j - i).

Input[1,8,6,2,5,4,8,3,7]Output49

Input[1,1]Output1

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

Try it yourself

Java

class Solution {
    public int maxArea(int[] height) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Start with the widest pair. The shorter wall is the bottleneck: pairing it with any wall further inside only shrinks the width while its height cap stays the same, so it can never do better — discard it and move inward.

PatternTwo Pointers

Instinct Sorted input, a pair/triple hitting a target, or something symmetric? Put one pointer at each end and move the one that can only improve things.

Memory hack Squeeze from both ends - every step throws away a whole row of the brute-force grid.

Open the Two Pointers guide →

Approaches

Brute ForceTry Every Pair of Walls

Time O(n²)Space O(1)

For every pair i < j, the water is min(height[i], height[j]) * (j - i). Track the maximum over all n(n-1)/2 pairs.

Java

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

Direct translation of the definition — times out for n = 10⁵.

OptimalTwo Pointers — Move the Shorter Wall

Time O(n)Space O(1)

Put left at 0 and right at n-1, record the area, then move whichever pointer has the shorter wall. Every pair skipped this way contains that shorter wall with a smaller width, so its area is ≤ the one just recorded — the optimum is never lost.

Java

public int maxArea(int[] height) {
    int maxArea = 0;
    int left = 0, right = height.length - 1;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        if (height[left] < height[right]) left++; // shorter wall can't improve
        else right--;
    }
    return maxArea;
}

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

l leftr right changed

1
1
l
8

6

2

5

4

8

3

7
r
min(1,7)×8=8 → l++
2
1

8
l
6

2

5

4

8

3

7
r
min(8,7)×7=49 → r--
3
1

8
l
6

2

5

4

8

3
r
7

min(8,3)×6=18 → r--
4
1

8
l
6

2

5

4

8
r
3

7

min(8,8)×5=40 → r--
…
1

8
l
6
r
2

5

4

8

3

7

all smaller → max=49 ✔

One pass, constant space; the greedy discard is provably safe.

Pro tip

Optional speed-up: after moving, keep skipping walls not taller than the one you just left — they can't beat it.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Pair of Walls	`O(n²)`	`O(1)`
Optimal	Two Pointers — Move the Shorter Wall	`O(n)`	`O(1)`

Common pitfalls

Moving the taller wall — can skip the optimal pair.
Confusing with Trapping Rain Water: here only two walls matter, inner walls are ignored.
Using max instead of min of the heights for the water level.

Interview tips

Give the brute force, then ask “which pairs can I rule out?”
Prove the greedy step: width shrinks, height is capped by the short wall.
On ties, moving either pointer is fine — mention it.

Pattern

Opposite-end two pointers with greedy discard → optimise a pair score that depends on distance and the min of two values.

My notes saved in this browser