Trapping Rain Water - water above every index

Worked first (Chen’s skyline): After rain, Chen’s city blocks [0,1,0,2,1,0,1,3,2,1,2,1] hold pools in the valleys. He does not need the single widest pair of towers (Day 47). He needs, for every block, how deep the puddle is on that rooftop. Formula: water above i is limited by the shorter of the tallest block to the left and the tallest to the right, minus the block’s own height. Sum = 6.

The problem

trap([0,1,0,2,1,0,1,3,2,1,2,1]) → 6
trap([4,2,0,3,2,5]) → 9
trap([5,5,5]) → 0   // nowhere to pool

Water above index i is bounded by the tallest bar on its left and on its right:

water[i] = max(0, min(leftMax[i], rightMax[i]) − height[i])

Sum over all i. Ends never hold water (no bound on one side).

Per-index table (classic example)

Heights [0,1,0,2,1,0,1,3,2,1,2,1]. leftMax[i] / rightMax[i] include bar i (then subtract height).

i	h	Lmax	Rmax	min−h
0	0	0	3	0
1	1	1	3	0
2	0	1	3	1
3	2	2	3	0
4	1	2	3	1
5	0	2	3	2
6	1	2	3	1
7	3	3	3	0
8	2	3	2	0
9	1	3	2	1
10	2	3	2	0
11	1	3	1	0

Water cells: 1+1+2+1+1 = 6. Peaks and ends contribute 0.

Approach 1: Brute — scan L/R max per index

function trapBrute(height) {
let water = 0;
const n = height.length;
for (let i = 0; i < n; i++) {
  let left = 0, right = 0;
  for (let j = 0; j <= i; j++) left = Math.max(left, height[j]);
  for (let j = i; j < n; j++) right = Math.max(right, height[j]);
  water += Math.min(left, right) - height[i];
}
return water;
}

O(n²). Lab n=2K: 24,046 μs median.

Approach 2: Precompute leftMax / rightMax

function trapPrecompute(height) {
const n = height.length;
if (!n) return 0;
const L = new Array(n), R = new Array(n);
L[0] = height[0];
for (let i = 1; i < n; i++) L[i] = Math.max(L[i - 1], height[i]);
R[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; i--) R[i] = Math.max(R[i + 1], height[i]);
let water = 0;
for (let i = 0; i < n; i++) water += Math.min(L[i], R[i]) - height[i];
return water;
}

O(n) time, O(n) space. Clear interview middle step — state this first for correctness.

Approach 3: Two pointers — O(1) space

function trap(height) {
let l = 0, r = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;
while (l < r) {
  if (height[l] < height[r]) {
    if (height[l] >= leftMax) leftMax = height[l];
    else water += leftMax - height[l];
    l++;
  } else {
    if (height[r] >= rightMax) rightMax = height[r];
    else water += rightMax - height[r];
    r--;
  }
}
return water;
}

Why the two-pointer rule works

Process the side whose current height is smaller. That side’s water is limited by its own running max (the opposite side is at least as tall right now, so the min bound is this side’s max).

• If height[l] < height[r], left is the tighter side for index l — use leftMax.
• If left bar is a new max, update leftMax (no water on a peak).
• Else add leftMax − height[l].

Same converging skeleton as Day 47, but you accumulate per-index water instead of tracking a global max area.

Two-pointer micro-trace

Short array [4,2,0,3,2,5] → answer 9. Start l=0,r=5, leftMax=rightMax=0.

step	h[l],h[r]	action	water Δ	total
1	4 < 5	leftMax=4; l→1	0	0
2	2 < 5	add 4−2; l→2	+2	2
3	0 < 5	add 4−0; l→3	+4	6
4	3 < 5	add 4−3; l→4	+1	7
5	2 < 5	add 4−2; l→5	+2	9

Right pointer never moved — right wall stayed the taller bound the whole time. When the right side is smaller, mirror the logic with rightMax.

Day 47 vs Day 53

Dimension	Day 47 Container	Day 53 Trapping
Question	Max water between two lines	Total water above all bars
Formula	min(h[i],h[j]) × (j−i)	Σ max(0, min(Lmax,Rmax) − h[i])
Two-ptr move	Move shorter height	Process side with smaller height (bound)
Output	One number (max area)	One number (sum of water)

Complexity honesty

Precompute and two-ptr are both O(n) time. The lab gap (15.7× at n=2K) is mostly allocation and memory traffic for the two extra arrays — not a different Big-O. Interview: state O(n)/O(n) first (clear correctness), then offer O(1) space two-ptr as the upgrade.

Monotonic stack (optional path)

Another O(n) solution walks left to right with a stack of indices of decreasing heights. When a taller bar appears, pop the stack: each pop closes a valley and adds a horizontal water slab width × (bounded height − bottom). Same answer; different mental model. Two-ptr is enough for NeetCode; know the stack exists for follow-ups.

Lab — Node, 30-run median

Seeded heights 0..99. The benchmark script and standalone write-up are not included in this repository.

Approach	n=500 (μs)	n=2K (μs)	n=10K (μs)
Brute O(n²)	1,434.0	24,046.3	skip
Precompute L/R	33.8	136.2	263.3
Two pointers	2.1	8.7	43.3

Headlines (n=2K): two-ptr is 2,764× vs brute (24,046 → 8.7 μs) and 15.7× vs precompute (136.2 → 8.7 μs) — same Big-O, less allocation.

What breaks? — Anti-patterns

• Using Day 47 max-area code for trapping — one pair vs sum over indices. Fix: per-index min(Lmax,Rmax) − h.
• Forgetting ends hold zero water — two-ptr grows bounds on peaks without adding there.
• leftMax as max strictly left of i (off-by-one) — water goes negative or wrong. Fix: maxes include i, then subtract height[i].
• Sorting heights — order is the terrain; sorting destroys the map.
• Moving the taller pointer “to go faster” — breaks the tighter-bound invariant (same family of bug as moving the tall wall on Day 47).

How it connects

• Day 47 (Container): two walls, one area. Today: every bar is a potential pool floor.
• Day 40 (Two Sum II): converge L/R; different predicate (sum vs bound maxes).
• Day 39 (Palindrome): converge + skip; here converge + running maxes.
• Day 19 (Prefix/suffix): precompute L/R max is the same “scan both ways” DNA as prefix products.

Transfer questions

1. Why can two pointers use O(1) space when precompute needs O(n)?
2. If the array is strictly increasing, how much water is trapped? Why?
3. On [4,2,0,3,2,5], after the first step leftMax=4 and l=1 — what water is added at index 2 and why is the right wall “safe”?
4. How would you adapt this to trap water in a 2D height map (interview follow-up)?

What you should be able to do

• Write water[i] = min(Lmax,Rmax) − h[i] and sum it.
• Implement precompute then upgrade to two-ptr O(1) space.
• Contrast Day 47 (one pair) vs Day 53 (every index) in one sentence.
• Quote the lab: 2,764× vs brute, 15.7× vs precompute at n=2K.

Interview version (60s)

“Trapping rain water: for each bar, depth is min(tallest left, tallest right) minus height. I precompute both max arrays in O(n) time and space, then mention two pointers that maintain running maxes from both ends in O(1) space — process the side with the smaller height because that side’s bound is tight. Lab: at n=2K, two-ptr is about 2,764× faster than brute and 15.7× faster than precompute from less allocation. Not the same problem as container-with-most-water, which maximizes one pair.”

Quiz

Your teach step

Close this lesson. Write the “Explain like I’m 10” and the “60-second LinkedIn version” from memory. Focus on: water[i] = min(Lmax,Rmax) − h; Day 47 vs 53; 2,764× / 15.7× benches. Post it, and paste the link.

Questions? Ask the agent — monotonic stack code, or 2D trap follow-up. Parked serial Day 53; you live from Day 24 (MVCC). Next prep empty is 54+.