Google — Trapping Rain Water II (3D BFS + Min-Heap)

Problem Statement#

Given an m x n matrix of non-negative integers representing elevation heights, compute how much water can be trapped after rain.

Constraints:

• m == heightMap.length
• n == heightMap[0].length
• 1 <= m, n <= 200
• 0 <= heightMap[i][j] <= 2 * 10^4

Input:  heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4

Input:  heightMap = [[3,3,3,3,3],[3,0,0,0,3],[3,0,0,0,3],[3,0,0,0,3],[3,3,3,3,3]]
Output: 27

Why This Problem Matters#

Trapping Rain Water II (LeetCode 407) is Google's go-to hard problem for candidates who have already solved the 1D version (LeetCode 42). Google uses it in senior engineer onsites to test whether candidates can extend 1D spatial reasoning to 3D and identify the correct data structure — a min-heap for boundary processing — without prompting.

The key insight requires understanding that water at any interior cell is bounded by the minimum height along the shortest "wall path" to the boundary. This is not the same as the minimum of the row/column maxima used in 1D. The min-heap BFS (Dijkstra-like) finds the minimum boundary height for each cell by expanding inward from the lowest boundary cells first.

This problem is rarely asked outside Google and hard-algorithm-focused interviews. However, it demonstrates mastery of priority queue BFS, which appears in many real-world shortest-path and flood-fill problems.

The Core Insight#

Initialize the min-heap with all boundary cells (height, row, col). Mark all boundary cells as visited. Repeatedly pop the minimum-height cell from the heap. For each unvisited neighbor, the water trapped at that neighbor is max(0, current_min_height - neighbor_height). The "effective height" of the neighbor when it joins the heap is max(current_min_height, neighbor_height) — because if the neighbor is taller than current_min_height, it becomes a new wall for cells behind it.

This is exactly Dijkstra's algorithm on the 2D grid with height as the edge weight.

Visual Dry Run#

Simple 3x3 grid: boundary cells form the outer ring, center is 0:

3 3 3
3 0 3
3 3 3

Actually 3x3 center cell traps 3-0=3 water → total=3 (walls are height 3, center is 0).

Solution (Optimal)#

import heapq
 
class Solution:
    def trapRainWater(self, heightMap: list) -> int:
        if not heightMap or len(heightMap) < 3 or len(heightMap[0]) < 3:
            return 0
 
        m, n = len(heightMap), len(heightMap[0])
        visited = [[False] * n for _ in range(m)]
        heap = []
 
        # Push all boundary cells
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    heapq.heappush(heap, (heightMap[i][j], i, j))
                    visited[i][j] = True
 
        water = 0
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
 
        while heap:
            h, i, j = heapq.heappop(heap)
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
                    visited[ni][nj] = True
                    water += max(0, h - heightMap[ni][nj])
                    heapq.heappush(heap, (max(h, heightMap[ni][nj]), ni, nj))
 
        return water

var trapRainWater = function(heightMap) {
    const m = heightMap.length, n = heightMap[0].length;
    if (m < 3 || n < 3) return 0;
 
    const visited = Array.from({length: m}, () => new Array(n).fill(false));
    // Simple min-heap via sorted array (replace with proper heap for large inputs)
    const heap = [];
 
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 || i === m-1 || j === 0 || j === n-1) {
                heap.push([heightMap[i][j], i, j]);
                visited[i][j] = true;
            }
        }
    }
    heap.sort((a, b) => a[0] - b[0]);
 
    let water = 0;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
 
    while (heap.length > 0) {
        const [h, i, j] = heap.shift();
        for (const [di, dj] of dirs) {
            const ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                visited[ni][nj] = true;
                water += Math.max(0, h - heightMap[ni][nj]);
                heap.push([Math.max(h, heightMap[ni][nj]), ni, nj]);
                heap.sort((a, b) => a[0] - b[0]);
            }
        }
    }
 
    return water;
};

Time: O(m * n * log(m * n)) — each cell pushed/popped from the heap once Space: O(m * n) — visited array and heap

Common Mistakes#

• Initializing the heap with only corners instead of all boundary cells — misses water near edges
• Not updating the effective height to max(current_min, neighbor_height) when pushing — uses wrong wall height
• Forgetting to mark boundary cells as visited during initialization — they get processed twice
• Using BFS without a heap (standard BFS uses FIFO) — must process lowest cells first
• Applying the 1D two-pointer approach directly — does not generalize to 2D correctly

Interview Tips#

• Connect to 1D Trapping Rain Water: "In 2D, water is bounded by the minimum wall height along any path to the boundary"
• Explain why we need a min-heap: "We must process the lowest boundary cell first — like Dijkstra"
• The key formula: water += max(0, current_wall - neighbor_height) and push max(current_wall, neighbor_height)
• Mention that this is Dijkstra's algorithm on a grid where edge weight is the barrier height
• Google may accept a clean pseudocode explanation followed by the Python implementation

Follow-up Questions#

• How does this differ from 1D Trapping Rain Water? — 1D uses two pointers; 2D requires heap-based BFS from boundary
• What if the grid has no interior cells? — Return 0 immediately; grids with fewer than 3 rows/cols hold no water
• How would you solve this with parallel processing? — Process boundary layers in parallel; synchronize at each depth
• What is the minimum grid size that can trap water? — 3x3 grid; a single interior cell surrounded by taller boundary
• How do you visualize which cells hold water? — Track max(0, effective_height - cell_height) per cell and display

Key Takeaways#

• Trapping Rain Water II extends 1D to 2D: water at a cell is bounded by the minimum wall on any path to the boundary
• Initialize the min-heap with all boundary cells — they define the initial walls
• Pop the minimum-height cell; for each unvisited neighbor: add max(0, popped_height - neighbor_height) to water
• Push the neighbor with effective height max(popped_height, neighbor_height) — preserves the wall for cells behind it
• This algorithm is Dijkstra's on a 2D grid where the "shortest path" is the lowest-height path to boundary
• Time is O(mn log mn) — each of mn cells is pushed/popped from the heap exactly once
• Google tests this as a senior-level extension of 1D rain water to verify 3D spatial reasoning and heap-based BFS mastery