Hints — p28 Trapping Rain Water

Read one at a time.

Hint 1 — Per-column thinking. For each column i, ignore everything else. How tall is the water above it? Answer: bounded by the SHORTER of the tallest bar to the left and the tallest bar to the right. Formula: water[i] = max(0, min(maxLeft[i], maxRight[i]) - h[i]). Total = sum.

Hint 2 — Naive O(N²) → speedup. Naive: for each i, scan left and right for the maxes. O(N²). Speedup: precompute maxLeft[i] in one left-to-right pass and maxRight[i] in one right-to-left pass. Then sum. O(N) time, O(N) space. Solution A. Ship this first.

Hint 3 — Can we drop the arrays? Two pointers lo, hi, running leftMax, rightMax. Whenever h[lo] < h[hi], you know rightMax ≥ h[hi] > h[lo], so the water at lo is determined by leftMax ALONE (the right side is guaranteed taller). Update leftMax = max(leftMax, h[lo]), accumulate leftMax - h[lo], advance lo. Symmetric for the other side. O(N) time, O(1) space. Solution B.

Hint 4 — Order matters in the two-pointer. Update leftMax BEFORE computing leftMax - h[lo]. Otherwise on a new tallest-so-far bar you’d compute a negative.

Hint 5 — Stack approach (advanced). Walk left to right. Maintain a decreasing stack of indices. When the current bar i exceeds the stack top, the top is a “trough bottom” — pop it; the new top is the left wall, i is the right wall. Water from this strip = (min(h[left], h[i]) - h[bottom]) * (i - left - 1). Repeat. Each index pushed/popped once → O(N). Solution C. This is the bridge to monotonic-stack problems (Histogram, Daily Temperatures).

If still stuck: all three implementations in solution.py. Read Solution A first, then Solution B with the move-rule proof in README.md section 6.3.