Container With Most Water: 5 Brilliant Moves That Win Fast

Two lines, one container, max water. Sounds trivial. It filters ruthlessly.

The obvious code checks every pair. That's O(n^2) — dead past 10,000 lines. You'll code it fast, feel good for a minute, then watch the stress test stall.

The fix is two pointers at the ends, always retiring the shorter line. Each step kills one hopeless candidate. That's O(n) time, O(1) space, eight lines. The code's easy; the proof's the interview. Learn both.

Area Is Capped by the Shorter Line, Never the Taller One

Given heights array h with n vertical lines, pick i < j maximizing min(h[i],h[j]) × (j - i). Water rises to the shorter line; width is the index gap. Example [1,8,6,2,5,4,8,3,7] gives 49: lines 8 (index 1) and 7 (index 8) hold min(8,7) = 7 over gap 8 - 1 = 7, so 7 x 7 = 49.

Constraints reach n = 10^5, heights to 10^4. O(n^2) pairs (~5×10^9) are hopeless. Answer fits 32-bit but Python ints make that moot. Smoke test: [1,1] → 1, [] → 0.

Walk [1,8,6,2,5,4,8,3,7]: (1,7) area 8 → move left (1 shorter). (8,7) area 7×7=49 → move right (7 shorter). (8,3) 3×6=18 → move right. (8,8) 8×5=40 → either; move left. (6,8) 6×4=24 → move left... best stays 49. One sweep, eight steps.

Testing Every Pair of Lines Is O(n^2) on 10^5 Heights

Brute force: every pair (i,j), compute min × gap, keep max. O(n^2) time, O(1) space. At n = 10^5 that's ~5×10^9 area computations — minutes to hours. Even n = 10^4 (50M pairs) misses the limit in Python.

No hash-map rescue exists: area couples values with positions, so lookup tricks don't apply. Sorting destroys indices. The pair structure forces either quadratic enumeration or the greedy insight — there is no middle ground worth coding.

Interview play: 'All pairs is O(n^2) — dead at 10^5. The shorter line caps area, so I'll converge from the ends retiring it.' Two sentences, then code. Anything longer wastes the clock.

Two Pointers: Always Move the Shorter Wall Inward

Place left = 0, right = n-1, best = 0. While left < right: best = max(best, min(h[left],h[right]) × (right-left)); if h[left] < h[right]: left += 1 else: right -= 1. (Ties: either side; moving right is conventional.)

Proof sketch: let the shorter side be h[left] ≤ h[right]. Every pair (left, k) with k < right is narrower than the current width and capped by the same height h[left] — so none can beat the best achievable with left fixed, which is at most h[left] × (right-left), already recorded. Hence left can be retired with no optimum lost. Symmetric for the right. Each step retires one line: n-1 steps, O(1) each → O(n) time, O(1) space. Every line is read; O(n) is optimal.

Equal heights: retiring either side is safe by the same argument (both bounds equal the recorded area's cap). Optional skip of equal runs saves constant steps.

The Two-Pointer Solution in Full Python

The code above is the complete LeetCode submission. Note the area is measured before the pointer moves, using the pre-move width — trace [1,1]: width 1, heights tie, area = 1×1 = 1, right retreats, loop ends, returns 1. Trace the big example: best climbs 8 → 49 → stays, returns 49.

Complexity: O(n) time, O(1) space. No imports, no lists, no slices — safe past n = 10^5.

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0
        while left < right:
            width = right - left
            if height[left] < height[right]:
                area = height[left] * width
                left += 1
            else:
                area = height[right] * width
                right -= 1
            if area > best:
                best = area
        return best

Two Lines Only, Equal Heights and Zero-Height Walls

Empty and single-element return 0 (loop never runs). Two elements return min × 1. All-equal heights return 1 × (n-1) — the widest pair. Strictly decreasing [5,4,3,2,1] resolves to 6 (5×... pairs: (5,1) gap 4 → 4; (5,2) gap 3 → 6; best 6). Strictly increasing mirrors it.

The disguised-quadratic trap: max(height[left:right]) or any slice inside the loop. Each slice costs O(n); n slices restore O(n^2). Grep the loop body — it must contain only indexing, arithmetic, and pointer moves.

Why a Single Pass From Both Ends Is Optimal

Time O(n): n-1 iterations, O(1) work each. Space O(1): three integers. Both optimal — each height must be read once (time floor), and only pointers plus best need storage (space floor).

Whiteboard closer: 'Converge from the ends, retire the shorter line, measure before moving.' Then bridge: 'The same shorter-side logic with running maxima gives Trapping Rain Water.' That bridge answers the follow-up before it's asked.