Google — Trapping Rain Water II (3D BFS + Min-Heap)

[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
→ 4

import heapq

def trapRainWater(heightMap):
    if len(heightMap) < 3 or len(heightMap[0]) < 3:
        return 0
    m, n = len(heightMap), len(heightMap[0])
    heap = []
    visited = [[False] * n for _ in range(m)]

    for r in range(m):
        for c in [0, n-1]:
            heapq.heappush(heap, (heightMap[r][c], r, c))
            visited[r][c] = True
    for c in range(n):
        for r in [0, m-1]:
            heapq.heappush(heap, (heightMap[r][c], r, c))
            visited[r][c] = True

    total = 0
    while heap:
        h, r, c = heapq.heappop(heap)
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
                visited[nr][nc] = True
                total += max(0, h - heightMap[nr][nc])
                heapq.heappush(heap, (max(h, heightMap[nr][nc]), nr, nc))
    return total

function trapRainWater(hm) {
    const m=hm.length,n=hm[0].length;
    if(m<3||n<3) return 0;
    const vis=Array.from({length:m},()=>new Array(n).fill(false));
    const heap=[]; let total=0;
    const push=(h,r,c)=>{heap.push([h,r,c]);let i=heap.length-1;while(i>0){const p=(i-1)>>1;if(heap[p][0]>heap[i][0]){[heap[p],heap[i]]=[heap[i],heap[p]];i=p;}else break;}};
    const pop=()=>{[heap[0],heap[heap.length-1]]=[heap[heap.length-1],heap[0]];const v=heap.pop();let i=0;while(true){let l=2*i+1,r=2*i+2,mi=i;if(l<heap.length&&heap[l][0]<heap[mi][0])mi=l;if(r<heap.length&&heap[r][0]<heap[mi][0])mi=r;if(mi===i)break;[heap[i],heap[mi]]=[heap[mi],heap[i]];i=mi;}return v;};
    for(let r=0;r<m;r++)for(const c of[0,n-1])if(!vis[r][c]){vis[r][c]=true;push(hm[r][c],r,c);}
    for(let c=0;c<n;c++)for(const r of[0,m-1])if(!vis[r][c]){vis[r][c]=true;push(hm[r][c],r,c);}
    while(heap.length){const [h,r,c]=pop();for(const[dr,dc]of[[-1,0],[1,0],[0,-1],[0,1]]){const nr=r+dr,nc=c+dc;if(nr>=0&&nr<m&&nc>=0&&nc<n&&!vis[nr][nc]){vis[nr][nc]=true;total+=Math.max(0,h-hm[nr][nc]);push(Math.max(h,hm[nr][nc]),nr,nc);}}}
    return total;
}

import java.util.*;
public int trapRainWater(int[][] hm) {
    int m=hm.length,n=hm[0].length; if(m<3||n<3)return 0;
    boolean[][] vis=new boolean[m][n];
    PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    for(int r=0;r<m;r++)for(int c:new int[]{0,n-1})if(!vis[r][c]){vis[r][c]=true;pq.offer(new int[]{hm[r][c],r,c});}
    for(int c=0;c<n;c++)for(int r:new int[]{0,m-1})if(!vis[r][c]){vis[r][c]=true;pq.offer(new int[]{hm[r][c],r,c});}
    int total=0,[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};
    while(!pq.isEmpty()){int[]top=pq.poll();for(int[]d:dirs){int nr=top[1]+d[0],nc=top[2]+d[1];if(nr>=0&&nr<m&&nc>=0&&nc<n&&!vis[nr][nc]){vis[nr][nc]=true;total+=Math.max(0,top[0]-hm[nr][nc]);pq.offer(new int[]{Math.max(top[0],hm[nr][nc]),nr,nc});}}}
    return total;
}

#include <queue>
#include <vector>
using namespace std;
int trapRainWater(vector<vector<int>>& hm) {
    int m=hm.size(),n=hm[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<>> pq;
    for(int r=0;r<m;r++)for(int c:{0,n-1})if(!vis[r][c]){vis[r][c]=true;pq.push({hm[r][c],r,c});}
    for(int c=0;c<n;c++)for(int r:{0,m-1})if(!vis[r][c]){vis[r][c]=true;pq.push({hm[r][c],r,c});}
    int total=0,dirs[]={-1,0,1,0,-1};
    while(!pq.empty()){auto[h,r,c]=pq.top();pq.pop();for(int d=0;d<4;d++){int nr=r+dirs[d],nc=c+dirs[d+1];if(nr>=0&&nr<m&&nc>=0&&nc<n&&!vis[nr][nc]){vis[nr][nc]=true;total+=max(0,h-hm[nr][nc]);pq.push({max(h,hm[nr][nc]),nr,nc});}}}
    return total;
}

/* C: same min-heap BFS — struct-based priority queue with boundary seeding */