Trapping Rain Water (LeetCode 42)
You're given n non-negative integers height describing an elevation map, where every bar is width 1. Work out the total volume of water this terrain would trap after rain.
Worked Examples
height = [0,1,0,2,1,0,1,3,2,1,2,1]6height = 0 | left_max = 2 | right_max = 3
Water = min(2, 3) - 0 = 2 units
At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.
If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!
- Unseen Interior Peaks: If
h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water atLis capped byleft_max. It can only spill left! - Order-of-Operations Bug: Always update
left_max = max(left_max, h[L])before subtracting to ensure you never add negative water. - Outer Edges Trap Zero: Indices
0andn - 1can never hold water because there are no outer containing walls.
height = [4,2,0,3,2,5]9height = 2 | left_max = 4 | right_max = 5
Water = min(4, 5) - 2 = 2 units
At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.
If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!
- Unseen Interior Peaks: If
h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water atLis capped byleft_max. It can only spill left! - Order-of-Operations Bug: Always update
left_max = max(left_max, h[L])before subtracting to ensure you never add negative water. - Outer Edges Trap Zero: Indices
0andn - 1can never hold water because there are no outer containing walls.
4 and 5, water fills each gap up to height 4: 2 + 4 + 1 + 2 = 9 units.⚖️Formal Constraints & Bounds
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
Core Insight
Do not scan left/right max arrays separately unless doing the two-pointer variant. With a monotonic stack, every popped 'valley' bar is resolved exactly once: the moment a bar tall enough to act as its right wall appears, its trapped water is width * (min(leftWall, rightWall) - valleyHeight).
Real-World Scenario & Production Applications
Reservoir capacity estimation from terrain elevation profiles, gutter/drainage sizing in civil engineering, and catchment-volume modeling in flood simulations.
Subproblems & Recurrence Decomposition3 Phases
Maintain a stack of indices whose heights are non-increasing from bottom to top -- each entry is a bar still waiting for a wall tall enough to trap water above it.
stack = [] # indices, heights non-increasing bottom to top
total = 0Step-by-Step Execution Trace Table
i | Height h[i] | Monotonic Stack Action | Popped Valley | Bounded Width (i - left - 1) | Bounded Height (min(hL, hR) - h_mid) | Water Volume Added |
|---|---|---|---|---|---|---|
| 0 | 0 | Push 0 | — | — | — | 0 |
| 1 | 1 | Pop 0 (trough 0), Push 1 | 0 | No left wall 0 | — | 0 |
| 2 | 0 | Push 2 | — | — | — | 0 |
| 3 | 2 | Pop 2 (trough 0) | 2 | Left wall: idx 1 (h=1), Right wall: idx 3 (h=2) | min(1, 2) - 0 = 1 | 1 * (3 - 1 - 1) = 1 |
| Push 3 | — | — | — | Total: 1 |
| 1 | stack = [] # indices, values non-increasing |
| 2 | total = 0 |
| 3 | for i, h in enumerate(values): |
| 4 | while stack and values[stack[-1]] < h: |
| 5 | valley_i = stack.pop() |
| 6 | if not stack: |
| 7 | break |
| 8 | left_i = stack[-1] |
| 9 | width = i - left_i - 1 |
| 10 | bounded_height = min(values[left_i], h) - values[valley_i] |
| 11 | total += width * bounded_height |
| 12 | stack.append(i) |
| 13 | return total |
Conceptual Narrative
While the two-pointer approach computes trapped water vertically column-by-column, the monotonic stack computes water horizontally in layered slabs, revealing the structural geometry of water basins.
🧭 Conceptual Foundation & Pattern Intuition
Water is trapped wherever a lower elevation bar (a valley floor) is enclosed by taller bars on both its left and right sides. The monotonic stack evaluates water horizontally in rectangular water slabs:
- A Monotonic Decreasing Stack stores indices of bars whose heights are strictly decreasing. These bars represent potential valley floors and left boundary walls.
- When an incoming bar at index is taller than
height[stack[-1]], we have discovered a right wall! - We pop the valley floor:
mid = stack.pop(). - If the stack is now empty, there is no left wall; water spills to the left, so no water is trapped.
- If the stack is non-empty, the new top of the stack is the left wall
left = stack[-1]. - The water level is bounded by the shorter of the two walls minus the floor height: \text{bounded_height} = \min(\text{height}[left], \text{height}[i]) - \text{height}[mid]
- The horizontal width of the water slab is:
- The trapped water slab volume \text{bounded_height} \times \text{width} is added to the total.
🪣 The Analogy: Filling Horizontal Steps in an Underground Quarry
Imagine an uneven stone quarry being flooded with water from above. You don't measure the water by drilling vertical core samples down each column. Instead, you fill the quarry layer by layer from the bottom up. Each time you encounter a dip between two stone ledges, you pour concrete between the left ledge and right ledge across that flat horizontal layer. If the water level rises further, the next layer spreads across an even wider span between taller outer walls.
🔑 Why It Works
Because each bar is pushed and popped at most once, this horizontal slab accumulation runs in amortized linear time and auxiliary space.
Empty stack after popping bottom: If the stack becomes empty after popping the trough/valley node, there is no left boundary wall to contain water. Bounded water is 0; guard with
if not stack: break.Bounded height formula: Water depth is determined by the shorter of the two bounding walls minus the trough height:
min(height[left], height[right]) - height[mid]. Subdividing incorrectly yields incorrect water slabs.Width formula off-by-one: The horizontal span between left wall and right wall is
right - left - 1. Forgetting-1overcounts water volume.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Trapping/pooling volume bounded by two walls in an elevation profile; monotonic stack lens on a problem that also has a two-pointer solution.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: stack holds indices in non-increasing height order; a popped index's trapped water is only resolvable once both a left wall (remaining on the stack) and a right wall (the current bar) exist.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Popping a valley when the stack becomes empty and still adding water: that valley has no left wall yet, so it contributes zero for now and must not be pushed back.
Using the popped valley's own height as one of the two walls instead of the new left-exposed stack top and the current bar.
Forgetting that width is
i - left_i - 1(strictly interior columns), noti - left_i.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I maintain a monotonic non-increasing stack of indices. For each bar, while the stack top is shorter than the current bar, I pop it as a resolved valley floor. If the stack is now empty, that valley has no left wall yet and traps nothing. Otherwise the new stack top is the left wall, width is
i - left_i - 1, and the water added iswidth * (min(height[left_i], h) - height[valley_i]). I push the current index. Every index is pushed once and popped at most once:O(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the loop structure: the outer for i, h in enumerate(height): visits each of the N bars once. The inner while stack and height[stack[-1]] < h: pops a bar as a resolved valley. Across the entire run, each index is pushed onto the stack exactly once and popped at most once, so total pops <= N. Total operations = N (pushes) + N (pops) = 2N, which is amortized O(N) linear time — identical amortization shape to Daily Temperatures and Largest Rectangle in Histogram earlier in this group.
O(N) Auxiliary
Look at memory allocation: the loop is iterative (O(1) call stack). Auxiliary memory is the stack list, which in the worst case (e.g. a strictly decreasing elevation profile) holds all N indices without ever popping. Auxiliary space is bounded by stack capacity O(N).
Derivation Progression
N total element pushes
Every bar index i is pushed onto the monotonic stack exactly once in the outer for loop.
≤ N total pops across all bars
The inner while loop pops a bar as a resolved valley when a taller bar arrives. Each index is popped at most once.
N pushes + N pops = 2N ⟹ O(N)
Total stack operations is bounded by 2N, yielding strictly amortized O(N) time.
Variable Definitions
Total number of bars in the elevation array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(N) Monotonic stack storing up to N bar indices in worst-case non-increasing order
O(1) Scalar running total of trapped water
Boundary Best / Worst Cases
strictly increasing then flat elevation (few pending valleys).
.
strictly decreasing elevation (all bars resolve only at the very end, or never).
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "how much water it can trap after raining". While the two-pointer approach measures vertical columns, the Monotonic Stack resolves horizontal water layers (basins) bounded between a left wall, a bottom floor, and a right wall.
. Time budget: . Space budget: stack memory.
Trapping Rain Water (LeetCode 42)
You're given n non-negative integers height describing an elevation map, where every bar is width 1. Work out the total volume of water this terrain would trap after rain.
Worked Examples
height = [0,1,0,2,1,0,1,3,2,1,2,1]6height = 0 | left_max = 2 | right_max = 3
Water = min(2, 3) - 0 = 2 units
At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.
If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!
- Unseen Interior Peaks: If
h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water atLis capped byleft_max. It can only spill left! - Order-of-Operations Bug: Always update
left_max = max(left_max, h[L])before subtracting to ensure you never add negative water. - Outer Edges Trap Zero: Indices
0andn - 1can never hold water because there are no outer containing walls.
height = [4,2,0,3,2,5]9height = 2 | left_max = 4 | right_max = 5
Water = min(4, 5) - 2 = 2 units
At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.
If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!
- Unseen Interior Peaks: If
h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water atLis capped byleft_max. It can only spill left! - Order-of-Operations Bug: Always update
left_max = max(left_max, h[L])before subtracting to ensure you never add negative water. - Outer Edges Trap Zero: Indices
0andn - 1can never hold water because there are no outer containing walls.
4 and 5, water fills each gap up to height 4: 2 + 4 + 1 + 2 = 9 units.⚖️Formal Constraints & Bounds
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
Core Insight
Do not scan left/right max arrays separately unless doing the two-pointer variant. With a monotonic stack, every popped 'valley' bar is resolved exactly once: the moment a bar tall enough to act as its right wall appears, its trapped water is width * (min(leftWall, rightWall) - valleyHeight).
Real-World Scenario & Production Applications
Reservoir capacity estimation from terrain elevation profiles, gutter/drainage sizing in civil engineering, and catchment-volume modeling in flood simulations.
Subproblems & Recurrence Decomposition3 Phases
Maintain a stack of indices whose heights are non-increasing from bottom to top -- each entry is a bar still waiting for a wall tall enough to trap water above it.
stack = [] # indices, heights non-increasing bottom to top
total = 0Step-by-Step Execution Trace Table
i | Height h[i] | Monotonic Stack Action | Popped Valley | Bounded Width (i - left - 1) | Bounded Height (min(hL, hR) - h_mid) | Water Volume Added |
|---|---|---|---|---|---|---|
| 0 | 0 | Push 0 | — | — | — | 0 |
| 1 | 1 | Pop 0 (trough 0), Push 1 | 0 | No left wall 0 | — | 0 |
| 2 | 0 | Push 2 | — | — | — | 0 |
| 3 | 2 | Pop 2 (trough 0) | 2 | Left wall: idx 1 (h=1), Right wall: idx 3 (h=2) | min(1, 2) - 0 = 1 | 1 * (3 - 1 - 1) = 1 |
| Push 3 | — | — | — | Total: 1 |
| 1 | stack = [] # indices, values non-increasing |
| 2 | total = 0 |
| 3 | for i, h in enumerate(values): |
| 4 | while stack and values[stack[-1]] < h: |
| 5 | valley_i = stack.pop() |
| 6 | if not stack: |
| 7 | break |
| 8 | left_i = stack[-1] |
| 9 | width = i - left_i - 1 |
| 10 | bounded_height = min(values[left_i], h) - values[valley_i] |
| 11 | total += width * bounded_height |
| 12 | stack.append(i) |
| 13 | return total |
Conceptual Narrative
While the two-pointer approach computes trapped water vertically column-by-column, the monotonic stack computes water horizontally in layered slabs, revealing the structural geometry of water basins.
🧭 Conceptual Foundation & Pattern Intuition
Water is trapped wherever a lower elevation bar (a valley floor) is enclosed by taller bars on both its left and right sides. The monotonic stack evaluates water horizontally in rectangular water slabs:
- A Monotonic Decreasing Stack stores indices of bars whose heights are strictly decreasing. These bars represent potential valley floors and left boundary walls.
- When an incoming bar at index is taller than
height[stack[-1]], we have discovered a right wall! - We pop the valley floor:
mid = stack.pop(). - If the stack is now empty, there is no left wall; water spills to the left, so no water is trapped.
- If the stack is non-empty, the new top of the stack is the left wall
left = stack[-1]. - The water level is bounded by the shorter of the two walls minus the floor height: \text{bounded_height} = \min(\text{height}[left], \text{height}[i]) - \text{height}[mid]
- The horizontal width of the water slab is:
- The trapped water slab volume \text{bounded_height} \times \text{width} is added to the total.
🪣 The Analogy: Filling Horizontal Steps in an Underground Quarry
Imagine an uneven stone quarry being flooded with water from above. You don't measure the water by drilling vertical core samples down each column. Instead, you fill the quarry layer by layer from the bottom up. Each time you encounter a dip between two stone ledges, you pour concrete between the left ledge and right ledge across that flat horizontal layer. If the water level rises further, the next layer spreads across an even wider span between taller outer walls.
🔑 Why It Works
Because each bar is pushed and popped at most once, this horizontal slab accumulation runs in amortized linear time and auxiliary space.
Empty stack after popping bottom: If the stack becomes empty after popping the trough/valley node, there is no left boundary wall to contain water. Bounded water is 0; guard with
if not stack: break.Bounded height formula: Water depth is determined by the shorter of the two bounding walls minus the trough height:
min(height[left], height[right]) - height[mid]. Subdividing incorrectly yields incorrect water slabs.Width formula off-by-one: The horizontal span between left wall and right wall is
right - left - 1. Forgetting-1overcounts water volume.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Trapping/pooling volume bounded by two walls in an elevation profile; monotonic stack lens on a problem that also has a two-pointer solution.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: stack holds indices in non-increasing height order; a popped index's trapped water is only resolvable once both a left wall (remaining on the stack) and a right wall (the current bar) exist.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Popping a valley when the stack becomes empty and still adding water: that valley has no left wall yet, so it contributes zero for now and must not be pushed back.
Using the popped valley's own height as one of the two walls instead of the new left-exposed stack top and the current bar.
Forgetting that width is
i - left_i - 1(strictly interior columns), noti - left_i.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I maintain a monotonic non-increasing stack of indices. For each bar, while the stack top is shorter than the current bar, I pop it as a resolved valley floor. If the stack is now empty, that valley has no left wall yet and traps nothing. Otherwise the new stack top is the left wall, width is
i - left_i - 1, and the water added iswidth * (min(height[left_i], h) - height[valley_i]). I push the current index. Every index is pushed once and popped at most once:O(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the loop structure: the outer for i, h in enumerate(height): visits each of the N bars once. The inner while stack and height[stack[-1]] < h: pops a bar as a resolved valley. Across the entire run, each index is pushed onto the stack exactly once and popped at most once, so total pops <= N. Total operations = N (pushes) + N (pops) = 2N, which is amortized O(N) linear time — identical amortization shape to Daily Temperatures and Largest Rectangle in Histogram earlier in this group.
O(N) Auxiliary
Look at memory allocation: the loop is iterative (O(1) call stack). Auxiliary memory is the stack list, which in the worst case (e.g. a strictly decreasing elevation profile) holds all N indices without ever popping. Auxiliary space is bounded by stack capacity O(N).
Derivation Progression
N total element pushes
Every bar index i is pushed onto the monotonic stack exactly once in the outer for loop.
≤ N total pops across all bars
The inner while loop pops a bar as a resolved valley when a taller bar arrives. Each index is popped at most once.
N pushes + N pops = 2N ⟹ O(N)
Total stack operations is bounded by 2N, yielding strictly amortized O(N) time.
Variable Definitions
Total number of bars in the elevation array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(N) Monotonic stack storing up to N bar indices in worst-case non-increasing order
O(1) Scalar running total of trapped water
Boundary Best / Worst Cases
strictly increasing then flat elevation (few pending valleys).
.
strictly decreasing elevation (all bars resolve only at the very end, or never).
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "how much water it can trap after raining". While the two-pointer approach measures vertical columns, the Monotonic Stack resolves horizontal water layers (basins) bounded between a left wall, a bottom floor, and a right wall.
. Time budget: . Space budget: stack memory.