Trapping Rain Water II solution and explanation

import heapq

def trapRainWater(heightMap):
    if not heightMap or not heightMap[0]:
        return 0

    m, n = len(heightMap), len(heightMap[0])
    visited = [[False] * n for _ in range(m)]
    heap = []
    
    # Push all the boundary cells into the heap
    for i in range(m):
        for j in range(n):
            if i == 0 or j == 0 or i == m - 1 or j == n - 1:
                heapq.heappush(heap, (heightMap[i][j], i, j))
                visited[i][j] = True

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    trappedWater = 0

    while heap:
        height, x, y = heapq.heappop(heap)

        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                trappedWater += max(0, height - heightMap[nx][ny])
                heapq.heappush(heap, (max(height, heightMap[nx][ny]), nx, ny))
                visited[nx][ny] = True

    return trappedWater

import java.util.PriorityQueue;

class Solution {
    private class Cell {
        int height, x, y;
        Cell(int h, int i, int j) { this.height = h; this.x = i; this.y = j; }
    }

    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) return 0;

        int m = heightMap.length, n = heightMap[0].length;
        PriorityQueue<Cell> pq = new PriorityQueue<>((a, b) -> a.height - b.height);
        boolean[][] visited = new boolean[m][n];

        // Push all the boundary cells into the heap
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                    pq.add(new Cell(heightMap[i][j], i, j));
                    visited[i][j] = true;
                }
            }
        }

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int trappedWater = 0;

        while (!pq.isEmpty()) {
            Cell cell = pq.poll();

            for (int[] d : directions) {
                int nx = cell.x + d[0], ny = cell.y + d[1];

                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny]) continue;

                trappedWater += Math.max(0, cell.height - heightMap[nx][ny]);
                pq.add(new Cell(Math.max(cell.height, heightMap[nx][ny]), nx, ny));
                visited[nx][ny] = true;
            }
        }

        return trappedWater;
    }
}

#include <vector>
#include <queue>
#include <functional>

using namespace std;

class Solution {
public:
    struct Cell {
        int x, y, height;
        Cell(int height, int x, int y) : height(height), x(x), y(y) {}
        bool operator>(const Cell& other) const { return height > other.height; }
    };

    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty()) return 0;

        int m = heightMap.size(), n = heightMap[0].size();
        priority_queue<Cell, vector<Cell>, greater<Cell>> pq;
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                    pq.push(Cell(heightMap[i][j], i, j));
                    visited[i][j] = true;
                }
            }
        }

        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int trappedWater = 0;

        while (!pq.empty()) {
            Cell cell = pq.top(); pq.pop();

            for (auto& dir : directions) {
                int nx = cell.x + dir[0], ny = cell.y + dir[1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    trappedWater += max(0, cell.height - heightMap[nx][ny]);
                    pq.push(Cell(max(cell.height, heightMap[nx][ny]), nx, ny));
                    visited[nx][ny] = true;
                }
            }
        }

        return trappedWater;
    }
};

var trapRainWater = function(heightMap) {
    if (!heightMap || !heightMap.length || !heightMap[0].length) return 0;
    
    const m = heightMap.length, n = heightMap[0].length;
    const visited = Array.from({ length: m }, () => Array(n).fill(false));
    const heap = new MinPriorityQueue({ priority: x => x.height });

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 || j === 0 || i === m - 1 || j === n - 1) {
                heap.enqueue({ height: heightMap[i][j], x: i, y: j });
                visited[i][j] = true;
            }
        }
    }

    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let trappedWater = 0;

    while (!heap.isEmpty()) {
        const { element: { height, x, y } } = heap.dequeue();

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

            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                trappedWater += Math.max(0, height - heightMap[nx][ny]);
                heap.enqueue({ height: Math.max(height, heightMap[nx][ny]), x: nx, y: ny });
                visited[nx][ny] = true;
            }
        }
    }

    return trappedWater;
};

using System;
using System.Collections.Generic;

public class Solution {
    public class Cell : IComparable<Cell> {
        public int height, row, col;
        public Cell(int h, int r, int c) { height = h; row = r; col = c; }
        public int CompareTo(Cell other) => height.CompareTo(other.height);
    }

    public int TrapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.Length == 0 || heightMap[0].Length == 0) return 0;

        int m = heightMap.Length, n = heightMap[0].Length;
        var pq = new SortedSet<Cell>();
        bool[,] visited = new bool[m, n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                    pq.Add(new Cell(heightMap[i][j], i, j));
                    visited[i, j] = true;
                }
            }
        }

        int[][] directions = new int[][] {
            new int[] {1, 0}, new int[] {-1, 0},
            new int[] {0, 1}, new int[] {0, -1}
        };
        int trappedWater = 0;

        while (pq.Count > 0) {
            var cell = pq.Min;
            pq.Remove(cell);

            foreach (var dir in directions) {
                int nx = cell.row + dir[0], ny = cell.col + dir[1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx, ny]) {
                    trappedWater += Math.Max(0, cell.height - heightMap[nx][ny]);
                    pq.Add(new Cell(Math.Max(cell.height, heightMap[nx][ny]), nx, ny));
                    visited[nx, ny] = true;
                }
            }
        }

        return trappedWater;
    }
}

from collections import deque

def trapRainWater(heightMap):
    if not heightMap or not heightMap[0]:
        return 0

    m, n = len(heightMap), len(heightMap[0])
    visited = [[False] * n for _ in range(m)]
    bfs_queue = deque()
    
    # Initialize BFS queue with border cells
    for i in range(m):
        for j in range(n):
            if i == 0 or j == 0 or i == m - 1 or j == n - 1:
                bfs_queue.append((i, j))
                visited[i][j] = True

    trappedWater = 0

    while bfs_queue:
        x, y = bfs_queue.popleft()

        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy

            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                if heightMap[nx][ny] < heightMap[x][y]:
                    trappedWater += heightMap[x][y] - heightMap[nx][ny]
                    heightMap[nx][ny] = heightMap[x][y]  # Update the height to mark flooded level
                bfs_queue.append((nx, ny))
                visited[nx][ny] = True

    return trappedWater

function trapRainWater(heightMap: number[][]): number {
    const m = heightMap.length;
    const n = heightMap[0].length;
    const vis: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
    const pq = new PriorityQueue<number[]>((a, b) => a[0] - b[0]);
    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) {
                pq.enqueue([heightMap[i][j], i, j]);
                vis[i][j] = true;
            }
        }
    }

    let ans = 0;
    const dirs = [-1, 0, 1, 0, -1];
    while (!pq.isEmpty()) {
        const [h, i, j] = pq.dequeue();
        for (let k = 0; k < 4; ++k) {
            const x = i + dirs[k];
            const y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                ans += Math.max(0, h - heightMap[x][y]);
                vis[x][y] = true;
                pq.enqueue([Math.max(h, heightMap[x][y]), x, y]);
            }
        }
    }
    return ans;
}

func trapRainWater(heightMap [][]int) (ans int) {
	m, n := len(heightMap), len(heightMap[0])
	pq := hp{}
	vis := make([][]bool, m)
	for i, row := range heightMap {
		vis[i] = make([]bool, n)
		for j, v := range row {
			if i == 0 || i == m-1 || j == 0 || j == n-1 {
				heap.Push(&pq, tuple{v, i, j})
				vis[i][j] = true
			}
		}
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for len(pq) > 0 {
		p := heap.Pop(&pq).(tuple)
		for k := 0; k < 4; k++ {
			x, y := p.i+dirs[k], p.j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] {
				ans += max(0, p.v-heightMap[x][y])
				vis[x][y] = true
				heap.Push(&pq, tuple{max(p.v, heightMap[x][y]), x, y})
			}
		}
	}
	return
}

type tuple struct{ v, i, j int }
type hp []tuple

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }