08. Trapping Rain Water II (3D Surface)

Difficulty:HardPattern:3D Min-Heap Boundary Inward SearchTime:O(M * N log(M * N))Space:O(M * N)

Given an $m \times n$ integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

How It Works & Algorithmic Design

Solves using Min-Heap Priority Queue Grid Boundary Shrinking:

Boundary Priority Queue: Push all outer boundary cells (r, c, height) into Min-Heap. Mark cells as visited.
Min-Height Processing: Maintain running maxBoundaryHeight = 0. While heap is not empty:
- Pop smallest boundary cell (r, c, h).
- Update maxBoundaryHeight = Math.max(maxBoundaryHeight, h).
- Evaluate 4 neighbors (nr, nc):
  - If unvisited: mark visited, accumulate trapped water Math.max(0, maxBoundaryHeight - heightMap[nr][nc]), and push neighbor to Min-Heap.

Why This Approach Works Best

Shrinking boundaries inward from lowest boundary height simulates water containment physics in $O(m \cdot n \log(m \cdot n))$ time.

Example Walkthrough

Input Grid: [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]

3D terrain matrix.

Water Volume: Inner valleys hold 4 total units of water.

Physics containment sum.

Output: 4

Trapped volume.

Answer: Trapping Rain Water II 3D implementation

function trapRainWater(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));
  const heap = []; // Simulated Min-heap array
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (r === 0 || r === m - 1 || c === 0 || c === n - 1) {
        visited[r][c] = true;
        heap.push([heightMap[r][c], r, c]);
      }
    }
  }
  heap.sort((a, b) => a[0] - b[0]);
  let water = 0, maxBoundary = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (heap.length) {
    const [h, r, c] = heap.shift();
    maxBoundary = Math.max(maxBoundary, h);
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < m && nc < n && !visited[nr][nc]) {
        visited[nr][nc] = true;
        if (heightMap[nr][nc] < maxBoundary) water += maxBoundary - heightMap[nr][nc];
        heap.push([heightMap[nr][nc], nr, nc]);
        heap.sort((a, b) => a[0] - b[0]);
      }
    }
  }
  return water;
}

💡 Pop lowest boundary height from priority queue and expand inward to trap surface water.

Key Takeaways

Boundary items must be pushed into Priority Queue first.
Water spill height is determined by lowest surrounding wall.
Runs in $O(M \cdot N \log(M \cdot N))$ time.