Trapping Rain Water II LeetCode 407 Guide

LeetCode 407 Trapping Rain Water II gives you an m x n integer matrix called heightMap representing the elevation of each cell on a 2D terrain. After it rains, water pools on the terrain and flows off the edges. Your task is to compute the total volume of water that can be trapped — meaning the sum of water held in every cell that cannot drain to the boundary.

Water flows in four directions (up, down, left, right) and escapes to the ground if it can reach the boundary of the grid. A cell traps water only when it is completely surrounded by higher walls in every direction that lead to the boundary. The trapped volume at each cell equals the difference between the effective water level and the cell's own height, as long as that difference is positive.

The constraints require an efficient approach: heightMap can be up to 200 x 200, so a brute-force simulation is infeasible. The key insight is that water level at each interior cell is determined by the lowest boundary wall that forms a complete ring around it — and a BFS min-heap processes exactly that information from the outside in.

In the classic 1D Trapping Rain Water (LeetCode 42), the two-pointer approach works because the water level at each position depends only on two values: the maximum height to its left and the maximum height to its right. Water at position i is min(maxLeft, maxRight) - height[i]. With only two directions to consider, a single left pointer and a single right pointer moving inward can maintain these maximums in O(n) time.

In 2D the boundary is an entire perimeter — every cell has four directions to consider, and the "walls" surrounding any interior cell form a complex ring rather than a simple left-right pair. The effective water level at an interior cell is not just the min of two maximums but the minimum height along the lowest path from that cell to any boundary cell. This path-based minimum cannot be computed with a simple two-pointer scan.

The 2D case requires a global view of the boundary structure. We need to know, for each interior cell, what is the lowest wall that prevents water from escaping to the outside. This is precisely what a min-heap BFS from the boundary computes — it processes cells in order of their effective water level, ensuring that when we reach any interior cell, we already know the tightest constraint on its water level.

The algorithm initializes by pushing all boundary cells into a min-heap, each entry stored as (height, row, col). All boundary cells are immediately marked as visited since water flows off the edges from them — they never trap water themselves. The min-heap ensures that the cell with the lowest height is always processed first.

At each step, pop the cell with the minimum height from the heap. This cell defines the current water level. For each of its four unvisited neighbors, check whether the neighbor's height is less than the current water level. If it is, the neighbor is below the effective waterline and traps water equal to waterLevel - neighbor.height. Push the neighbor into the heap with height max(neighbor.height, waterLevel) — this propagates the effective water level inward.

The propagation of max(neighbor.height, waterLevel) is the key insight: if the neighbor is taller than the current water level, the new effective water level rises to the neighbor's own height. Future cells reached through this neighbor will be bounded by the taller wall, not the lower one we came from. This correctly models water being held back by the tallest wall on the path from any interior cell to the boundary.

Processing cells from lowest to highest height ensures we never overcount. When a cell is popped from the min-heap, we already know the tightest (lowest) wall that separates it from the boundary. Any future path to the boundary through a different route must pass through a wall at least as high — because all lower cells have already been processed. This guarantees that the water level assigned to each cell is exactly the minimum boundary height on the optimal escape route.

This is structurally identical to Dijkstra's shortest path algorithm. Replace "shortest distance" with "minimum wall height on the path to the boundary" and the analogy is exact. The min-heap plays the role of Dijkstra's priority queue: cells are relaxed in non-decreasing order of their effective water level, and once a cell is popped it is finalized — its water level is optimal and will not be improved by any later path.

The correctness relies on one property: the effective water level only increases or stays the same as we move inward. A cell processed later can only have a water level >= the cell that triggered it, because we take max(neighbor.height, waterLevel). This monotone non-decreasing property is what allows the greedy heap-based approach to work correctly without needing to revisit cells.

A boolean visited array of size m x n prevents processing the same cell twice. Boundary cells are marked visited before the main loop begins. Interior cells are marked visited when they are pushed onto the heap — not when they are popped. Marking on push rather than pop is correct here because once a cell is enqueued with the correct water level, any later path to it would only produce an equal or higher water level (due to the monotone property), so the first enqueue is optimal.

The water calculation at each cell is straightforward: water = max(0, waterLevel - heightMap[nr][nc]). If the neighbor is taller than the current water level, it traps zero water (the max with 0 handles this). If it is shorter, it traps the difference. The total trapped water is the running sum of these per-cell contributions across all interior cells reached during the BFS.

Edge cases to handle: grids with fewer than 3 rows or 3 columns have no interior cells at all and return 0 immediately. A flat grid where all heights are equal traps no water. A grid where the boundary is taller than all interior cells will have every interior cell trap water equal to the minimum boundary height minus its own height — the algorithm handles all of these naturally without special-casing.

In Python, use heapq for the min-heap. Initialize with heapq.heapify on all boundary cells. The main loop uses heapq.heappop to get the minimum, then iterates over the four neighbors with a directions list [(0,1),(0,-1),(1,0),(-1,0)]. Time complexity is O(m*n*log(m*n)) because each of the m*n cells is pushed and popped from the heap at most once, and each heap operation costs O(log(m*n)). Space complexity is O(m*n) for the heap and visited array.

In Java, use java.util.PriorityQueue<int[]> with a comparator on the first element (height). Boundary initialization iterates the four edges separately. The directions are stored as a 2D int array. Java's PriorityQueue.offer() and poll() mirror Python's heappush and heappop. The visited boolean array is initialized to false by default. The implementation is otherwise structurally identical to the Python version.

Both implementations share the same invariant: cells are processed in non-decreasing order of effective water level. The heap entry stores (effectiveWaterLevel, row, col) — note that after propagation, this may be higher than the cell's actual height. The effectiveWaterLevel stored in the heap is what matters for computing water at subsequent neighbors, not the raw heightMap value.

Trapping Rain Water I (LeetCode 42) is the essential precursor — solve it first to understand the water level concept before extending to 2D. Pacific Atlantic Water Flow (LeetCode 417) uses a similar multi-source BFS from two sets of boundary cells to determine which cells can reach each ocean. Both problems share the "fill from the boundary inward" mental model.

Swim in Rising Water (LeetCode 778) is structurally the closest relative — it asks for the minimum time to reach the bottom-right corner where time equals the maximum height encountered on the path. This is the same min-heap BFS but tracking the maximum height on the path rather than accumulating trapped water. Solving both problems back-to-back cements the Dijkstra-like heap traversal pattern.

For further depth in the BFS + heap family, Minimum Cost to Make at Least One Valid Path in a Grid (LeetCode 1368) uses 0-1 BFS (deque) for a similar grid traversal. Cut Off Trees for Golf Event (LeetCode 675) chains multiple BFS calls on a grid. Mastering LeetCode 407 gives you the foundation for all heap-based grid traversal problems — the combination of min-heap ordering and multi-source initialization is a recurring pattern in hard-level interview problems.