Trapping Rain Water II (LeetCode 407)
You're given an m x n grid of integers heightMap, where each cell's value is the height of a unit column of terrain at that position. After rain falls across the whole map, work out how much water settles and stays trapped between the columns, and return that total volume.
Worked Examples
heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]4heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]10⚖️Formal Constraints & Bounds
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104
Core Insight
Always expanding from the currently lowest boundary cell (a min-heap frontier, exactly like Dijkstra's relaxation order) guarantees every cell's trapped-water contribution is finalized the instant it is popped.
Real-World Scenario & Production Applications
Flood-fill terrain modeling for civil engineering drainage simulations and multi-source shortest-path routing over weighted grids.
Subproblems & Recurrence Decomposition3 Phases
Every border cell of the grid is an initial "wall." Push each as (height, r, c) into a min-heap and mark it visited -- this is the starting container before any water is measured.
visited = [[False] * cols for _ in range(rows)]
min_heap = []
for r in range(rows):
for c in range(cols):
if r in (0, rows - 1) or c in (0, cols - 1):
heapq.heappush(min_heap, (heightMap[r][c], r, c))
visited[r][c] = TrueStep-by-Step Execution Trace Table
| Step | Popped (height, r, c) | Neighbor Flooded | Water Added | Running Total |
|---|---|---|---|---|
| 1 | (1, 0, 0) | (1, 1) height 2 | max(0, 1-2)=0 | 0 |
| 2 | (1, 2, 3) | (1, 3) height 3 | max(0, 1-3)=0 | 0 |
| 3 | (2, 1, 0) | (1, 1) already visited | -- | 0 |
| ... | ... | (1, 2) height 1 | max(0, 3-1)=2 | 2 |
| ... | ... | (2, 2) height 3 | max(0, 3-3)=0 | 4 |
| 1 | min_heap = every border cell as (height, r, c) |
| 2 | mark every border cell visited |
| 3 | while min_heap: |
| 4 | height, r, c = heappop(min_heap) |
| 5 | for each unvisited neighbor (nr, nc): |
| 6 | visited[nr][nc] = True |
| 7 | total_water += max(0, height - grid[nr][nc]) |
| 8 | heappush(min_heap, (max(height, grid[nr][nc]), nr, nc)) |
| 9 | return total_water |
Conceptual Narrative
Trapping Rain Water in 1D used two pointers racing inward from both ends. In 2D, there is no single "inward" direction — water can leak out through any of the four sides of an interior cell. The heap replaces the two pointers with a frontier of border cells that always expands from its currently weakest point.
🧭 Conceptual Foundation & Pattern Intuition
Imagine building a dam by starting with the outer rim of the terrain as your initial "wall." Water trapped at any interior cell cannot rise higher than the lowest point on the boundary enclosing it — exactly like a bathtub whose walls have one low spot: water spills out there first. So the algorithm always processes the lowest cell currently on the frontier, because that cell is the binding constraint for everything still unvisited next to it.
🏟️ The Analogy: Flooding a Terrain From the Outside In
Picture the entire grid as a walled city seen from above, where every border tile is part of the city wall. You flood the terrain starting from the shortest section of the wall — as if water were rising from the ocean outside and finding the weakest point in the perimeter first. Once you step over that weakest wall segment into the interior, the interior cell you land on immediately becomes part of the new wall (at whichever is taller: the old wall or the new cell), and its height determines whether the next cell inward gets flooded.
🔑 The Key Idea in the Code
The visited set plays the same role as Dijkstra's "finalized" set: once a cell is popped from the heap, its water contribution is permanently correct, because every cell still in the heap or unvisited is guaranteed to be reachable only through walls at least as tall as the one just popped.
Not initializing min-heap with all outer perimeter boundary cells: In 3D rain water, water spills off the 4 borders. All border cells of the grid must seed the initial min-heap and be marked visited.
Water trapped formula inversion: Water trapped at neighbor cell is
max(0, current_boundary_height - cell_height). Inverting the subtraction yields negative water quantities.Updating neighbor height when pushing to heap: When pushing an unvisited neighbor into the heap, its effective height is
max(current_boundary_height, cell_height). Pushing rawcell_heightleaks water below the true water level.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
2D grid + trap water + can leak in 4 directions + need the volume, not just max height.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: once a cell is popped from the min-heap, its trapped-water contribution is final -- every remaining cell is reachable only through walls at least as tall as the one just popped.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to mark border cells visited before seeding the heap (double-processes corners).
Using the neighbor's own height instead of max(height, neighbor_height) when pushing the new wall -- this lets water "leak" through a taller neighbor incorrectly.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I seed a min-heap with every border cell as the initial wall and mark them visited. I repeatedly pop the lowest wall cell; for each unvisited neighbor, I add max(0, height - neighbor_height) to the total, mark it visited, and push it back with height max(height, neighbor_height) since the wall can only grow. This is Dijkstra's relaxation order applied to water trapping: O(mn log(mn)) time, O(mn) space."
Complexity & Mathematical Proof
O(mn log(mn))
Look at the execution steps: Every one of the mn cells is pushed onto the heap exactly once and popped exactly once. Each heap operation costs O(log(mn)) since the heap can hold up to mn entries. Total: O(mn log(mn)).
O(mn) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The min-heap and the visited grid both scale with the number of cells, O(mn).
T(m, n) = mn · O(log(mn)) = O(mn log(mn))
Derivation Progression
O(m + n) border cells pushed
Every border cell is pushed once as the initial wall in O(log(mn)) each.
mn cells × O(log(mn)) heap ops
Each interior cell is popped once and its up-to-4 neighbors examined; each unvisited neighbor is pushed once.
O(mn log(mn))
Every cell contributes exactly one push and one pop across the whole run.
Variable Definitions
Number of rows in the height map
Number of columns in the height map
Memory Architecture & Bounds
O(1) Iterative
O(mn) Min-heap holds up to every cell
O(1) Single integer total
Boundary Best / Worst Cases
even on a flat grid (every cell still pushed/popped once).
.
on a deep single basin.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Trigger: "trapping rain water in a 2D elevation map". In 1D, water level is bounded by the minimum of the max-left and max-right walls. In 2D, water spills out through the lowest point on the entire outer perimeter! A Senior SWE recognizes Dijkstra-Style Inward Boundary Contraction via Min-Heap: the cell with the lowest boundary elevation governs spillover for adjacent unvisited interior cells.
cells. Time budget: heap operations, running well under 150ms.
Water elevation monotonically increases: when expanding to a neighbor with lower height, water is trapped, but the neighbor's effective boundary height becomes max(current_height, neighbor_height) before pushing to the heap.
Trapping Rain Water II (LeetCode 407)
You're given an m x n grid of integers heightMap, where each cell's value is the height of a unit column of terrain at that position. After rain falls across the whole map, work out how much water settles and stays trapped between the columns, and return that total volume.
Worked Examples
heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]4heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]10⚖️Formal Constraints & Bounds
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104
Core Insight
Always expanding from the currently lowest boundary cell (a min-heap frontier, exactly like Dijkstra's relaxation order) guarantees every cell's trapped-water contribution is finalized the instant it is popped.
Real-World Scenario & Production Applications
Flood-fill terrain modeling for civil engineering drainage simulations and multi-source shortest-path routing over weighted grids.
Subproblems & Recurrence Decomposition3 Phases
Every border cell of the grid is an initial "wall." Push each as (height, r, c) into a min-heap and mark it visited -- this is the starting container before any water is measured.
visited = [[False] * cols for _ in range(rows)]
min_heap = []
for r in range(rows):
for c in range(cols):
if r in (0, rows - 1) or c in (0, cols - 1):
heapq.heappush(min_heap, (heightMap[r][c], r, c))
visited[r][c] = TrueStep-by-Step Execution Trace Table
| Step | Popped (height, r, c) | Neighbor Flooded | Water Added | Running Total |
|---|---|---|---|---|
| 1 | (1, 0, 0) | (1, 1) height 2 | max(0, 1-2)=0 | 0 |
| 2 | (1, 2, 3) | (1, 3) height 3 | max(0, 1-3)=0 | 0 |
| 3 | (2, 1, 0) | (1, 1) already visited | -- | 0 |
| ... | ... | (1, 2) height 1 | max(0, 3-1)=2 | 2 |
| ... | ... | (2, 2) height 3 | max(0, 3-3)=0 | 4 |
| 1 | min_heap = every border cell as (height, r, c) |
| 2 | mark every border cell visited |
| 3 | while min_heap: |
| 4 | height, r, c = heappop(min_heap) |
| 5 | for each unvisited neighbor (nr, nc): |
| 6 | visited[nr][nc] = True |
| 7 | total_water += max(0, height - grid[nr][nc]) |
| 8 | heappush(min_heap, (max(height, grid[nr][nc]), nr, nc)) |
| 9 | return total_water |
Conceptual Narrative
Trapping Rain Water in 1D used two pointers racing inward from both ends. In 2D, there is no single "inward" direction — water can leak out through any of the four sides of an interior cell. The heap replaces the two pointers with a frontier of border cells that always expands from its currently weakest point.
🧭 Conceptual Foundation & Pattern Intuition
Imagine building a dam by starting with the outer rim of the terrain as your initial "wall." Water trapped at any interior cell cannot rise higher than the lowest point on the boundary enclosing it — exactly like a bathtub whose walls have one low spot: water spills out there first. So the algorithm always processes the lowest cell currently on the frontier, because that cell is the binding constraint for everything still unvisited next to it.
🏟️ The Analogy: Flooding a Terrain From the Outside In
Picture the entire grid as a walled city seen from above, where every border tile is part of the city wall. You flood the terrain starting from the shortest section of the wall — as if water were rising from the ocean outside and finding the weakest point in the perimeter first. Once you step over that weakest wall segment into the interior, the interior cell you land on immediately becomes part of the new wall (at whichever is taller: the old wall or the new cell), and its height determines whether the next cell inward gets flooded.
🔑 The Key Idea in the Code
The visited set plays the same role as Dijkstra's "finalized" set: once a cell is popped from the heap, its water contribution is permanently correct, because every cell still in the heap or unvisited is guaranteed to be reachable only through walls at least as tall as the one just popped.
Not initializing min-heap with all outer perimeter boundary cells: In 3D rain water, water spills off the 4 borders. All border cells of the grid must seed the initial min-heap and be marked visited.
Water trapped formula inversion: Water trapped at neighbor cell is
max(0, current_boundary_height - cell_height). Inverting the subtraction yields negative water quantities.Updating neighbor height when pushing to heap: When pushing an unvisited neighbor into the heap, its effective height is
max(current_boundary_height, cell_height). Pushing rawcell_heightleaks water below the true water level.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
2D grid + trap water + can leak in 4 directions + need the volume, not just max height.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: once a cell is popped from the min-heap, its trapped-water contribution is final -- every remaining cell is reachable only through walls at least as tall as the one just popped.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to mark border cells visited before seeding the heap (double-processes corners).
Using the neighbor's own height instead of max(height, neighbor_height) when pushing the new wall -- this lets water "leak" through a taller neighbor incorrectly.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I seed a min-heap with every border cell as the initial wall and mark them visited. I repeatedly pop the lowest wall cell; for each unvisited neighbor, I add max(0, height - neighbor_height) to the total, mark it visited, and push it back with height max(height, neighbor_height) since the wall can only grow. This is Dijkstra's relaxation order applied to water trapping: O(mn log(mn)) time, O(mn) space."
Complexity & Mathematical Proof
O(mn log(mn))
Look at the execution steps: Every one of the mn cells is pushed onto the heap exactly once and popped exactly once. Each heap operation costs O(log(mn)) since the heap can hold up to mn entries. Total: O(mn log(mn)).
O(mn) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The min-heap and the visited grid both scale with the number of cells, O(mn).
T(m, n) = mn · O(log(mn)) = O(mn log(mn))
Derivation Progression
O(m + n) border cells pushed
Every border cell is pushed once as the initial wall in O(log(mn)) each.
mn cells × O(log(mn)) heap ops
Each interior cell is popped once and its up-to-4 neighbors examined; each unvisited neighbor is pushed once.
O(mn log(mn))
Every cell contributes exactly one push and one pop across the whole run.
Variable Definitions
Number of rows in the height map
Number of columns in the height map
Memory Architecture & Bounds
O(1) Iterative
O(mn) Min-heap holds up to every cell
O(1) Single integer total
Boundary Best / Worst Cases
even on a flat grid (every cell still pushed/popped once).
.
on a deep single basin.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Trigger: "trapping rain water in a 2D elevation map". In 1D, water level is bounded by the minimum of the max-left and max-right walls. In 2D, water spills out through the lowest point on the entire outer perimeter! A Senior SWE recognizes Dijkstra-Style Inward Boundary Contraction via Min-Heap: the cell with the lowest boundary elevation governs spillover for adjacent unvisited interior cells.
cells. Time budget: heap operations, running well under 150ms.
Water elevation monotonically increases: when expanding to a neighbor with lower height, water is trapped, but the neighbor's effective boundary height becomes max(current_height, neighbor_height) before pushing to the heap.