Trapping Rain Water II

// C++
int trapRainWater(vector<vector<int>>& heightMap) {
    int m=heightMap.size(), n=heightMap[0].size();
    if (m<3||n<3) return 0;
    vector<vector<bool>> vis(m, vector<bool>(n, false));
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> minH;
    for (int i=0;i<m;i++) for(int j=0;j<n;j++) if(i==0||i==m-1||j==0||j==n-1){minH.push({heightMap[i][j],i,j});vis[i][j]=true;}
    int res=0;
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    while (!minH.empty()) {
        auto [h,r,c] = minH.top(); minH.pop();
        for (int d=0;d<4;d++) {
            int nr=r+dx[d], nc=c+dy[d];
            if (nr<0||nr>=m||nc<0||nc>=n||vis[nr][nc]) continue;
            vis[nr][nc]=true;
            res += max(0, h-heightMap[nr][nc]);
            minH.push({max(h,heightMap[nr][nc]),nr,nc});
        }
    }
    return res;
}

// Java
public int trapRainWater(int[][] heightMap) {
    int m=heightMap.length, n=heightMap[0].length;
    if (m<3||n<3) return 0;
    boolean[][] vis = new boolean[m][n];
    PriorityQueue<int[]> minH = new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(i==0||i==m-1||j==0||j==n-1){minH.offer(new int[]{heightMap[i][j],i,j});vis[i][j]=true;}
    int res=0;
    int[]dx={0,0,1,-1},dy={1,-1,0,0};
    while(!minH.isEmpty()){
        int[]p=minH.poll();
        for(int d=0;d<4;d++){
            int nr=p[1]+dx[d],nc=p[2]+dy[d];
            if(nr<0||nr>=m||nc<0||nc>=n||vis[nr][nc])continue;
            vis[nr][nc]=true;
            res+=Math.max(0,p[0]-heightMap[nr][nc]);
            minH.offer(new int[]{Math.max(p[0],heightMap[nr][nc]),nr,nc});
        }
    }
    return res;
}

# Python
import heapq

def trapRainWater(heightMap):
    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 = []
    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
    result = 0
    while heap:
        h, r, c = heapq.heappop(heap)
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                visited[nr][nc] = True
                result += max(0, h - heightMap[nr][nc])
                heapq.heappush(heap, (max(h, heightMap[nr][nc]), nr, nc))
    return result

// JavaScript
function trapRainWater(heightMap) {
    const m = heightMap.length, n = heightMap[0].length;
    if (m < 3 || n < 3) return 0;
    // Use sorted array as min-heap substitute
    const vis = Array.from({length: m}, () => Array(n).fill(false));
    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]); vis[i][j] = true;
        }
    }
    heap.sort((a, b) => a[0] - b[0]);
    let result = 0;
    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
    while (heap.length) {
        const [h, r, c] = heap.shift();
        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;
            result += Math.max(0, h - heightMap[nr][nc]);
            const nh = Math.max(h, heightMap[nr][nc]);
            let pos = heap.findIndex(x => x[0] >= nh);
            if (pos === -1) heap.push([nh, nr, nc]);
            else heap.splice(pos, 0, [nh, nr, nc]);
        }
    }
    return result;
}