Trapping Rain Water Problem: 6 Master Moves That Crack It

Trapping Rain Water is the Hard that haunts Medium solvers. The formula fits one line. The pointer logic breaks brains.

Brute force checks every bar against full left/right scans. That's O(n^2) — dead past 20,000 bars. The prefix-array middle ground works but costs O(n) memory you'll be asked to remove.

The two-pointer answer settles one bar per step using running maxima. That's O(n) time, O(1) space. The code is short; the invariant is subtle. You'll nail it once you see that the smaller-max side is always decided. Let's build that sight.

Water Over a Bar Depends on the Tallest Wall Either Side

Given elevation heights h[0..n-1], compute trapped rain water: at each index, depth = min(tallest left wall, tallest right wall) − h[i], floored at 0. Sum all depths. Example [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units. Check one slot: index 2 (height 0) has left max 1, right max 3 → min 1 − 0 = 1 unit.

Constraints reach n = 2×10^4+ with heights to 10^5. O(n^2) re-scans die; totals fit 32-bit but Python ints ignore that. Probes: [3,0,3] → 3, [5,4,3,2,1] → 0, [] → 0.

Walk [3,0,3]: left wall 3, right wall 3, middle depth min(3,3)−0 = 3. The middle bar's level is decided the moment both walls are known — that 'decided side' idea is the entire two-pointer proof.

Rescanning Left and Right Per Bar Costs O(n^2)

Brute force: per index scan left for max, scan right for max, add min − h. O(n^2) time, O(1) space. At n = 20,000 that's 400M scans — minutes past the limit. Correct formula, fatal delivery.

Prefix/suffix upgrade: two passes precompute left_max[] and right_max[], then one summation pass. O(n) time, O(n) space — the obviously-correct baseline worth presenting in interviews before compressing.

Interview play: 'Brute force is O(n^2) — dead. Prefix arrays make it O(n) space; I'll compress to pointers for O(1).' Three beats, then code the finale. Examiners score the staged reasoning.

Two Pointers: The Shorter Side Always Decides the Water

Maintain left, right pointers with left_max, right_max (tallest seen from each end). While left <= right: refresh the maxima from the current ends; if left_max <= right_max, the left side's level is decided (its min-bound can't exceed left_max regardless of the interior) — settle it: trapped += max(0, left_max − h[left]), left += 1. Else mirror on the right.

Proof sketch: when left_max <= right_max, the water level at left is min(left_max, true_right_max). Since true_right_max >= right_max >= left_max, the min equals left_max — decided. So measuring left now is exact. The symmetric argument holds rightward. Each step settles one bar: n steps, O(1) each → O(n) time, two maxima + total → O(1) space.

Relation to Container: both retire the bounded side; Container bounds area by the shorter line, Rain Water decides level by the smaller running max. Same instinct, richer state.

The Converging-Pointer Solution in Full Python

The code above is the complete LeetCode submission, using the equivalent height-comparison form: the lower current bar's side is settled (a standard variant — when h[left] < h[right], left's bound is decided by left_max since right holds a wall at least as tall). Trace [3,0,3]: left=3,right=3 tie → else-branch: right 3 ≥ max 0 → right_max=3, right=1. h[0]=3 < h[1]=0? No → else: h[1]=0 < 3 → trapped += 3. right=0. h[0]=3 vs h[0]... left=0,right=0: h equal → else: h[0]=3 ≥ right_max 3 → right_max=3, right=-1. Total 3. Correct.

Trace the big example: the sweep banks depths 1, 1, 1, 2, and 1 across the valleys, summing to 6. Returns 6. Complexity O(n)/O(1).

class Solution:
    def trap(self, height: list[int]) -> int:
        if not height:
            return 0
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        trapped = 0
        while left <= right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    trapped += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    trapped += right_max - height[right]
                right -= 1
        return trapped

Monotonic Slopes, Flat Terrain and Empty Input

Empty returns 0 via guard; single bar returns 0 (no walls). Monotonic runs trap 0 — the clamp/max-refresh structure guarantees non-negativity. Plateaus ([2,2,2]) trap 0: maxima refresh instead of accumulating. Sharp V ([5,0,5]) traps 5.

Large-input trap: max(height[:i]) slices inside the loop — each O(n), total O(n^2). The loop body must touch only indices, scalars, and pointer moves. Equal-height adjacent bars: handled by the else branch deterministically; no special code needed.

Why O(n) Time With O(1) Space Is Achievable Here

Time O(n): each bar settles once with O(1) work. Space O(1): two pointers, two maxima, one total. Both meet lower bounds — every bar must be read (time floor); the answer needs only counters (space floor).

Whiteboard closer: 'Smaller-max side is decided; settle it, bank the water, step inward.' Then bridge: '2D terrain (LeetCode 407) generalizes decided-sides with a heap; monotonic stacks give the valley-explicit O(n) alternative.' Hard solved, Harder previewed.