LeetCode Challenge Day 18 — 407. Trapping Rain Water II

Hey folks

This is Day 18 of my LeetCode streak 🚀.
Today’s problem is 407. Trapping Rain Water II — the 2D version of the classic Trapping Rain Water problem.
The challenge is to calculate how much water can be trapped in a grid surrounded by walls of different heights.

It’s a heap + BFS style problem that feels very similar to Dijkstra’s algorithm.

📌 Problem Statement

You are given an m x n integer matrix heightMap representing the height of each cell.
Return the total volume of rain water it can trap after raining.

Examples

• 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,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
  Output: 10

Constraints

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

💡 Intuition

In the 1D problem, trapped water depends on the minimum of the left and right walls.
In 2D, water depends on the lowest boundary around a cell.

So we use a min-heap priority queue:

• Start from all boundary cells (they define the walls).
• Always expand from the lowest wall.
• Keep track of the highest wall seen so far.
• If a neighbor is lower than this wall, it traps water equal to the difference.

🔑 Approach

1. Insert all boundary cells into a min-heap and mark them visited.
2. While the heap is not empty:
   • Pop the lowest cell.
   • Update the current wall = max(current wall, cell height).
   • For each neighbor not yet visited:
     • If its height < current wall → trap water = current wall - height.
     • Push the neighbor with height = max(current wall, neighbor height).
3. Return the total trapped water.

⏱️ Complexity Analysis

• Time complexity: O(m * n * log(m * n))
  Each cell is processed once, heap operations take log(m * n).

• Space complexity: O(m * n)
  For the visited matrix and heap storage.

🧑‍💻 Code (JavaScript)

/**
 * @param {number[][]} heightMap
 * @return {number}
 */
var trapRainWater = function(heightMap) {
  const m = heightMap.length;
  if (m === 0) return 0;
  const n = heightMap[0].length;
  if (m < 3 || n < 3) return 0;

  class MinHeap {
    constructor() { this.a = []; }
    _parent(i) { return ((i - 1) >> 1); }
    _l(i) { return (i << 1) + 1; }
    _r(i) { return (i << 1) + 2; }
    _swap(i, j) { [this.a[i], this.a[j]] = [this.a[j], this.a[i]]; }
    push(x) {
      this.a.push(x);
      this._up(this.a.length - 1);
    }
    _up(i) {
      while (i > 0) {
        const p = this._parent(i);
        if (this.a[p][0] <= this.a[i][0]) break;
        this._swap(i, p);
        i = p;
      }
    }
    pop() {
      if (this.a.length === 0) return null;
      const top = this.a[0];
      const last = this.a.pop();
      if (this.a.length) {
        this.a[0] = last;
        this._down(0);
      }
      return top;
    }
    _down(i) {
      const n = this.a.length;
      while (true) {
        let smallest = i;
        const l = this._l(i), r = this._r(i);
        if (l < n && this.a[l][0] < this.a[smallest][0]) smallest = l;
        if (r < n && this.a[r][0] < this.a[smallest][0]) smallest = r;
        if (smallest === i) break;
        this._swap(i, smallest);
        i = smallest;
      }
    }
    size() { return this.a.length; }
  }

  const heap = new MinHeap();
  const vis = Array.from({ length: m }, () => Array(n).fill(false));

  for (let r = 0; r < m; r++) {
    for (let c of [0, n - 1]) {
      heap.push([heightMap[r][c], r, c]);
      vis[r][c] = true;
    }
  }
  for (let c = 0; c < n; c++) {
    for (let r of [0, m - 1]) {
      if (!vis[r][c]) {
        heap.push([heightMap[r][c], r, c]);
        vis[r][c] = true;
      }
    }
  }

  let water = 0, currentWall = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  while (heap.size()) {
    const [h, r, c] = heap.pop();
    currentWall = Math.max(currentWall, h);

    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n || vis[nr][nc]) continue;
      vis[nr][nc] = true;

      const nh = heightMap[nr][nc];
      if (nh < currentWall) water += (currentWall - nh);

      heap.push([Math.max(nh, currentWall), nr, nc]);
    }
  }

  return water;
};

🧪 Edge Cases

Very small grids (m < 3 or n < 3) → cannot trap water.

Flat surfaces → no water trapped.

Deep pits fully surrounded by higher walls → maximum trapping possible.

🎥 Reflections

This problem is a great extension of the 1D trapping rain water logic into 2D. The key insight is to always expand from the lowest wall first, very similar to Dijkstra’s algorithm.

That’s it for Day 18 of my LeetCode journey! On to the next challenge 🔥

Happy Coding 👨‍💻