407.js

/** ------------------------------------------------------------------------------
 * 
 * 407. Trapping Rain Water II
 * Topics: Array, BFS, Heap, Matrix
 * https://leetcode.com/problems/trapping-rain-water-ii/?envType=daily-question&envId=2025-01-19
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[][]} heightMap
 * @return {number}
 */
var trapRainWater = function (heightMap) {
  const m = heightMap.length
  const n = heightMap[0].length

  if (m < 3 || n < 3) return 0

  const visited = Array.from({ length: m }, () => Array(n).fill(0))
  const minHeap = []

  const addToHeap = (x, y, height) => {
    minHeap.push([height, x, y])
    minHeap.sort((a, b) => a[0] - b[0])
    visited[x][y] = 1
  }

  for (let i = 0; i < m; i++) {
    addToHeap(i, 0, heightMap[i][0])
    addToHeap(i, n - 1, heightMap[i][n - 1])
  }
  for (let j = 1; j < n - 1; j++) {
    addToHeap(0, j, heightMap[0][j])
    addToHeap(m - 1, j, heightMap[m - 1][j])
  }

  let waterTrapped = 0
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]

  while (minHeap.length > 0) {
    const [height, x, y] = minHeap.shift()

    for (const [dx, dy] of directions) {
      const nx = x + dx
      const ny = y + dy

      if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
        waterTrapped += Math.max(0, height - heightMap[nx][ny])
        addToHeap(nx, ny, Math.max(height, heightMap[nx][ny]))
      }
    }
  }
  return waterTrapped
}

console.log(
  trapRainWater([
    [1, 4, 3, 1, 3, 2],
    [3, 2, 1, 3, 2, 4],
    [2, 3, 3, 2, 3, 1],
  ]),
)
console.log(
  trapRainWater([
    [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],
  ]),
)