Two Pointers — Container With Most Water

↗ LeetCode: Container With Most Water · Medium · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftBloomberg

Given n non-negative integer heights, find two vertical lines that form a container holding the maximum amount of water. Water volume = min(h[i], h[j]) × (j − i).

Example 1 — heights = [1,8,6,2,5,4,8,3,7] → 49 (indices 1 and 8: min(8,7)*7) Example 2 — heights = [1,1] → 1Constraints — 2 ≤ n ≤ 10⁵, 0 ≤ h[i] ≤ 10⁴. Brute enumerates every pair in O(n²) = 10¹⁰ ops at n=10⁵ (TLE past ~10 s). Two-pointer inward sweep — provably safe by monotonicity — is O(n) = 10⁵ ops = <5 ms.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force (all pairs)

Intuition. Try every pair (i, j); compute area; keep the max.

int maxAreaBrute(int[] h) {
    int best = 0, n = h.length;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            best = Math.max(best, Math.min(h[i], h[j]) * (j - i));
    return best;
}

Execution Trace

Brute — heights=[1,8,6,2,5,4,8,3,7]: sampling a few pairs

Step 1 / 3min(1,7)*8 = 8

Complexity — Time O(n²); Space O(1). Fails at n=10⁵.

---

Approach 2 — Two pointers from ends

Insight from brute. Start with the widest window [0, n-1]. Its area = min(h[0], h[n-1]) * (n-1). Moving the taller wall inward can only shrink the width; the height is capped by the shorter wall so the area can only decrease. Moving the shorter wall inward might find a taller neighbour and win.

Rule: always advance the pointer at the shorter wall.

int maxArea(int[] h) {
    int lo = 0, hi = h.length - 1, best = 0;
    while (lo < hi) {
        int area = Math.min(h[lo], h[hi]) * (hi - lo);
        best = Math.max(best, area);
        if (h[lo] < h[hi]) lo++;
        else               hi--;
    }
    return best;
}

Execution Trace

Two pointers — heights=[1,8,6,2,5,4,8,3,7]

Step 1 / 5min(1,7)*8=8. lo shorter → lo++

Complexity — Time O(n); Space O(1). Optimal.

Trap. Advancing the taller wall is provably wrong because the container's limiting dimension is the shorter wall — you'd shrink width without any chance of the height going up.

---

Try it yourself

Complexity summary

Approach	Time	Space
Brute force	O(n²)	O(1)
Two pointers	O(n)	O(1)

When to use which

• Interviewer opens cold → state brute, then jump to two-pointer with the correctness argument.
• Interviewer asks "why not move the taller wall?" → the exchange argument above.

✨AI Study CompanionBeta

Related problems (same ladder applies)

• Trapping Rain Water — two pointers + per-side max
• 3Sum — sort, fix pivot, two-pointer the tail
• Sort Colors — three-way partition (Dutch flag)
• Squares of a Sorted Array — two pointers from ends, fill back-to-front

Was this page helpful?