p28 — Trapping Rain Water

Source: LeetCode 42 · Hard · Topics: Array, Two Pointers, Dynamic Programming, Stack Companies (2024–2025 frequency): Google (very high), Amazon (high), Meta (high), Microsoft (high), Bloomberg (high), Apple (medium) Loop position: algorithm round, often the killer. This is the showcase problem.

1. Quick Context

Given n non-negative integers representing the elevation map where the width of each bar is 1, compute how much water it can trap after raining.

This problem is in a class of its own. It has three legitimate O(N) optimal solutions — each using a different algorithmic technique:

1. Prefix-suffix max arrays — O(N) time, O(N) extra space. Classic.
2. Two pointers — O(N) time, O(1) extra space. Elegant.
3. Monotonic decreasing stack — O(N) time, O(N) space. Processes water in horizontal strips.

The interviewer asks Trapping Rain Water specifically to see how many you know and which one you reach for first. Knowing one is Mid; knowing two is Senior; knowing all three and explaining when to prefer each is Staff+.

The core insight (shared by all three): water above index i is min(maxLeft[i], maxRight[i]) - height[i]. Each solution differs in how it computes that min.

This is also the bridge problem to monotonic stacks (Phase 02 Lab 05) — the stack solution previews patterns used in Largest Rectangle in Histogram, Daily Temperatures, etc.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/trapping-rain-water/

STOP. 30-min timer. This is Hard — try the prefix-max array first. The two-pointer optimization is hard to invent under pressure.

3. Prerequisite Concepts

• p27 — Container With Most Water (warmup; two-pointer pattern).
• Prefix sums / prefix maxes — running max from left and right.
• Monotonic stacks — phase-02-patterns/labs/lab-05-monotonic-stack.md.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Given a histogram height[0..n-1] of non-negative integers (each bar width 1), return the total volume of water trapped between bars after rain.”

Step 2 — Clarify:

• “What does ‘trapped’ mean physically?” — for each column i, water level is min(tallest bar to the left, tallest bar to the right); trapped water at i is max(0, that_level - height[i]).
• “Can heights be zero?” (Yes.)
• “Total volume or per-column?” (Total, an integer.)
• “Width of each bar?” (1 — fixed.)
• “Negative heights?” (No.)

Step 3 — Constraints: N ≤ 2×10⁴ for LC. All O(N) approaches comfortable.

Step 4 — Examples:

• [0,1,0,2,1,0,1,3,2,1,2,1] → 6.
• [4,2,0,3,2,5] → 9.
• [3,0,2,0,4] → 7.
• [] → 0. [1] → 0. [5,5,5] → 0.

Step 5 — Brute Force: For each index i, scan left for max, scan right for max, add min(L,R) - h[i]. O(N²). State, then pivot.

Step 6 — Complexity (optimal): O(N) time. Space varies by approach: O(N) (prefix arrays), O(1) (two-pointer), O(N) (stack).

Step 7 — Pattern Recognition: “Each cell’s contribution depends on a property of its left AND right context” → prefix-max array (precompute), or two-pointer (eliminate as you go), or monotonic stack (process boundaries as they’re confirmed).

Step 8 — Develop: See solution.py. All three implementations side-by-side.

Step 9 — Test: monotone increasing (0 water), monotone decreasing (0), V-shape, W-shape, plateaus, all-equal, empty.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Three solutions, one problem

6.1 The shared insight

For each column i, the water level above it is determined by the tallest bar to the left and the tallest bar to the right:

$$\text{water}(i) = \max(0, \min(\text{maxLeft}(i), \text{maxRight}(i)) - h[i])$$

Total water = sum over all i. The three solutions are three ways to evaluate this formula efficiently.

6.2 Solution A — Prefix-suffix max arrays (O(N), O(N) space)

Precompute maxLeft[i] = max(h[0..i]) in one left-to-right pass, maxRight[i] = max(h[i..n-1]) in one right-to-left pass. Then sum the formula in a third pass.

Why it’s the “default” solution: clearest and most directly mirrors the formula. Easy to write, easy to debug, easy to test. Use this when interviewer doesn’t push for space optimization.

6.3 Solution B — Two pointers (O(N), O(1) space)

Maintain lo, hi, leftMax, rightMax. Loop while lo < hi:

• If height[lo] < height[hi]: the water at lo is bounded by leftMax (because rightMax ≥ height[hi] > height[lo], so rightMax is at least as big as height[hi] which dominates height[lo], so the min is leftMax). Update leftMax, accumulate leftMax - height[lo], advance lo.
• Symmetric for the other side.

The subtle correctness argument: the move rule is “advance the side with the smaller current height.” This guarantees that the side we’re advancing has a confirmed taller side on the other end — so the water level at the advancing column is determined entirely by leftMax (or rightMax) on the same side. We don’t need the global rightMax because we know it’s at least height[hi] which already exceeds height[lo].

When to use: when interviewer asks “can you do it in O(1) space?” or as the senior signal.

6.4 Solution C — Monotonic decreasing stack (O(N), O(N) space)

Maintain a stack of indices with strictly decreasing heights. Walk left to right; when the current bar h[i] exceeds the top of the stack h[top]:

• Pop top. The popped index is a “trough bottom.”
• The “left wall” is now the new top of the stack; the “right wall” is i.
• Water added at this trough = (min(h[new_top], h[i]) - h[top]) * (i - new_top - 1). (A horizontal strip.)
• Repeat while the current bar still exceeds the (new) top.

This processes water in horizontal strips, one trough at a time. Each index is pushed once and popped once → O(N) total.

When to use:

• When the same problem is generalized (e.g., Largest Rectangle in Histogram — same stack pattern).
• When the interviewer specifically asks about the stack approach as a follow-up.
• When you want to demonstrate range of techniques.

6.5 Comparing the three

7. Anti-Pattern Analysis

1. O(N²) brute and shipping it. Easy to write but TLE on big inputs.
2. Computing max(maxLeft, maxRight) instead of min. Water level is the SHORTER wall (water spills over the shorter). Sign error.
3. Forgetting max(0, ...) — when h[i] exceeds both walls, the formula gives a negative; clamp to 0.
4. Two-pointer with leftMax = max(leftMax, height[lo]) AFTER computing water. Order matters: update leftMax FIRST, then compute leftMax - height[lo] (which is now ≥ 0).
5. Stack approach: forgetting the * (i - new_top - 1) width factor. Strip width is (right_wall - left_wall - 1).
6. Stack approach: pushing without checking equality. Equal-height stack tops are tricky — usually push (the formula handles equal heights naturally since strip height = 0).
7. Two-pointer with lo <= hi. At lo == hi, the column has walls on both sides equal to its own height — no water — wasted iteration. < cleaner.
8. Reading the input as floats when problem says non-negative integers. Rookie input-handling slip.

8. Skills & Takeaways

• Prefix-max arrays as a meta-pattern (extends to suffix-max, range queries, etc).
• Two-pointer with auxiliary state (running max from each side) — a step up from p27.
• Monotonic decreasing stack for “process when bound is confirmed” patterns.
• Multiple optimal solutions — recognize that one O(N) solution doesn’t preclude there being others with different tradeoffs.
• Horizontal-strips vs column-by-column decomposition of trapped water.

9. When to Move On

Move on when:

• You can write the prefix-max solution in under 8 minutes.
• You can write the two-pointer solution in under 12 minutes with the move-rule justification.
• You can write the stack solution in under 18 minutes.
• You can articulate the trade-offs in one sentence each.
• Your stress test runs all three vs brute on 500 random small arrays.
• You can pivot to LC 84 (Largest Rectangle in Histogram) using the same stack template.

10. Company Context

Google:

• The classic “let’s go deep” problem. Expect to be asked for ALL THREE solutions over 45 min.
• Bar for Staff+: invent a 4th solution (segment tree / sparse table) without prompting, even if not optimal.
• Scorecard phrase: “Algorithm + breadth — three O(N) solutions, articulated tradeoffs.”

Amazon:

• Often the second problem in an algorithm round. Bar Raiser will probe for the space-optimization.
• Scorecard phrase: “Strong — prefix-max naturally, then optimized to two-pointer when asked.”

Meta:

• Frequently paired with LC 84 (Histogram) in the same loop — stack pattern is the lesson.
• Scorecard phrase: “Algorithm — recognized stack pattern, generalized to histogram.”

Microsoft:

• Sometimes asked at the System Design boundary: “now process a streaming version where heights arrive in chunks.”
• Scorecard phrase: “Strong — prefix-max + thoughtful streaming discussion.”

Bloomberg:

• Frames as financial: “for each day, compute the underwater drawdown given an envelope of historical highs/lows.” Same algorithm.
• Scorecard phrase: “Pragmatic — recognized P&L underwater pattern.”

Apple:

• Often asked with the 2D variant (LC 407 Trapping Rain Water II) as a follow-up. Min-heap + BFS from boundary.
• Scorecard phrase: “Strong — 1D solutions + 2D extension via min-heap.”

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Prefix-max arrays solution.
• Correct formula min(maxLeft, maxRight) - h[i], clamped to 0.
• O(N) time, O(N) space stated.
• Edge cases handled.

Senior (L5):

• Reaches for two-pointer first OR upgrades from prefix-max to two-pointer when prompted.
• Articulates the move-rule justification.
• Knows the stack approach exists (may not implement fully in time).
• Notes 2D version exists.

Staff (L6):

• Implements BOTH two-pointer AND stack solutions cleanly.
• Articulates trade-offs.
• Connects stack approach to LC 84, LC 739, monotonic stack family.
• Discusses 2D version (LC 407) and outlines min-heap-from-boundary algorithm.

Principal (L7+):

• Discusses streaming variant: with append-only data, the prefix-max array can be maintained online but suffix-max can’t — solve with stack (deferred decisions).
• Discusses range-update generalization: if heights change dynamically, segment tree with range-max queries supports updates in O(log N) per change but full recompute is required for trapped water (O(N) per query). A more clever structure is open territory.
• Discusses parallelism: prefix-max parallelizes via parallel prefix-scan (Blelloch); two-pointer is inherently sequential.
• Discusses production: drainage simulation, GPU heatmap min-pooling, financial drawdown analysis.

13. Follow-up Q&A

Q1: O(1) extra space? A: Two-pointer approach (Solution B). Maintain leftMax, rightMax, lo, hi. Detailed proof: the side with the smaller current height has its water level determined entirely by that side’s running max.

Q2: 2D version (LC 407 Trapping Rain Water II). A: Heap-based BFS from the boundary. Push all boundary cells into min-heap with their heights. Pop smallest, visit unvisited neighbors: if neighbor height < current threshold, it traps threshold - height water and is pushed with threshold; otherwise pushed with its own height. O(MN log MN). The intuition: water “leaks” from the lowest point on the boundary first.

Q3: Heights are streaming (append-only). Can we maintain running answer? A: Each new bar might cause water to be “released” or “added” depending on heights around old positions — non-trivial. Stack approach generalizes: maintain monotonic decreasing stack of indices; when new bar arrives, pop and add trapped water as before. Total work O(N) amortized.

Q4: What if heights can update arbitrarily (point updates)? A: Hard. Segment tree supports range-max queries in O(log N), but trapped water at index i depends on global maxes — a single update can change trapped water at MANY indices. Best known: recompute in O(N) per update, or accept higher complexity for the dynamic version.

Q5: Compute trapped water in any SUBRANGE [l, r] quickly. A: Precompute prefix-max and suffix-max with sparse tables (O(N log N) preprocessing, O(1) range-max). For each query, recompute water column-by-column in O(r - l + 1) — no faster known.

14. Solution Walkthrough

See solution.py:

• trap_prefix_max(height) — Solution A. O(N) time, O(N) space.
• trap_two_pointer(height) — Solution B. O(N) time, O(1) space.
• trap_stack(height) — Solution C. O(N) time, O(N) space, monotonic decreasing stack.
• trap_brute(height) — O(N²) per-column scan, oracle.
• stress_test() — 500 random small arrays; all four implementations agree.
• edge_cases() — empty, single bar, monotone, V, W, plateau, LC canonical.

Run: python3 solution.py → “ALL TESTS PASSED”.

15. Beyond the Problem

Principal-engineer code review comment:

“Three solutions in one file is fine for teaching, NOT for production. In a real PR I want one solution, picked deliberately. For our drainage-simulation service we use the stack approach because it generalizes to our streaming gauge-readings model. For our financial-drawdown library we use prefix-max because the data is bounded and the extra space is fine. Don’t ship ‘three approaches’ code — ship the one you justified. The other two go in the docs as ‘considered alternatives’. Also: the two-pointer’s invariant comment should mention WHY rightMax dominates when we advance lo (h[lo] < h[hi] ≤ rightMax). Future readers will not derive that themselves under pressure.”

Connections forward:

• p27 — Container With Most Water: same two-pointer skeleton, different objective (max area vs sum of water).
• Phase 02 Lab 05 — Monotonic Stack: this is the bridge problem. Solution C is the template.
• LC 84 — Largest Rectangle in Histogram: same monotonic-stack pattern.
• LC 407 — Trapping Rain Water II: 2D version, heap-from-boundary BFS.
• Production: drainage simulation in civil engineering, water-management infrastructure planning, financial drawdown (“underwater” portfolio analysis), GPU image min/max pooling.
• Theoretical: the dual problem (maximum trapped water under a CHANGE in heights — Dilworth’s-like decomposition) is open research.