Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

&nbsp;
Example 1:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.


Example 2:

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


&nbsp;
Constraints:


	m == heightMap.length
	n == heightMap[i].length
	1 &lt;= m, n &lt;= 200
	0 &lt;= heightMap[i][j] &lt;= 2 * 104


import heapq
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        ROW, COL = len(heightMap), len(heightMap[0])

        pq = []
        heapq.heapify(pq)
        visited = {}
        
        for row in range(ROW):
            for col in range(COL):
                if row == 0 or row == ROW-1 or col == 0 or col == COL-1:
                    heapq.heappush(pq, (heightMap[row][col],row,col))
                    visited[(row,col)] = True
                    
        def getnbr(row,col):
            res = []
            if row-1 >=0:
                res.append((row-1,col))
            if col-1 >=0:
                res.append((row, col-1))
            if row+1 < ROW:
                res.append((row+1,col))
            if col+1 < COL:
                res.append((row, col+1))

            return res
        
        res = 0
        
        while pq:
            h, i, j = heapq.heappop(pq)
            
            for dx, dy in getnbr(i,j):
                if (dx,dy) not in visited:  
                    
                    res += max(0, h-heightMap[dx][dy])
                    
                    heapq.heappush(pq, (max(h, heightMap[dx][dy]),dx,dy))
                    visited[(dx,dy)] = True

        return res
class Solution {
    public class pair implements Comparable<pair>{
        int row;
        int col;
        int val;
        pair(int row, int col,int val){
            this.row = row;
            this.col = col;
            this.val = val;
        }
        public int compareTo(pair o){
            return this.val - o.val;
        }
    }
    int[][] dir = {{1,0},{0,-1},{-1,0},{0,1}};
    public int trapRainWater(int[][] heightMap) {
        int n = heightMap.length;
        int m = heightMap[0].length;
        
        PriorityQueue<pair> pq = new PriorityQueue<>();
        
        boolean[][] visited = new boolean[n][m];
        
        // add all the boundary elements in pq
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i == 0 || j == 0 || i == n-1 || j == m-1){
                    pq.add(new pair(i, j, heightMap[i][j]));
                    visited[i][j] = true;
                }
            }
        }
        
        int ans = 0;
        
        while(pq.size() > 0){
            pair rem = pq.remove();
            for(int i = 0; i < 4; i++){
                
                int rowdash = rem.row + dir[i][0];
                int coldash = rem.col + dir[i][1];
                
                if(rowdash >= 0 && coldash >= 0 && rowdash < n && coldash < m && visited[rowdash][coldash] == false){
                    visited[rowdash][coldash] = true;
                    if(heightMap[rowdash][coldash] >= rem.val){
                        pq.add(new pair(rowdash, coldash, heightMap[rowdash][coldash])); // boundary is updated
                    }else{
                        int waterstored = rem.val - heightMap[rowdash][coldash];
                        ans += waterstored;                                             // now this will act as a wall add in pq
                        pq.add(new pair(rowdash, coldash, heightMap[rowdash][coldash] + waterstored));
                    }
                }
            }
        }
        return ans;
    }
}
class Solution {
public:
	bool vis[201][201];                                                           //to keep track of visited cell
    int n,m;
    bool isValid(int i, int j){
        if(i<0 || i>=m || j<0 || j>=n || vis[i][j]==true)  return false;
        
        return true;
    }
    int trapRainWater(vector<vector<int>>& heightMap) {
        vector<vector<int>> dir {{1,0},{-1,0},{0,1},{0,-1}};          //direction Vector
        m = heightMap.size();   if(m==0)    return 0;                // m=0 is one edge case
        n = heightMap[0].size();
        memset(vis,false,sizeof(vis));
        priority_queue<pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>> , greater<pair<int,pair<int,int>>> >pq;                                // min heap w.r.t cell height
        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({heightMap[i][j],{i,j}});                          //pushing all outer cells in pq
                    vis[i][j]=true;
                }   
            }
        }
        int water = 0;
        int Height = INT_MIN;
        while(!pq.empty()){                                                       //normal BFS
            auto pr =  pq.top();
            pq.pop();
            int height = pr.first;
            int i = pr.second.first;
            int j = pr.second.second;
            Height = max(Height,height);
            for(int d=0;d<4;d++){                                            //iterating through direction vector
                int x = i + dir[d][0];
                int y = j + dir[d][1];
                if(isValid(x,y)){
                   water += max(0, Height - heightMap[x][y]);      //just adding the diff between cell height and surrounding height
                   vis[x][y]=true;
                   pq.push({heightMap[x][y],{x,y}});
                }
            }            
        }
        return water;
		}
	};
const dir = [[0, -1], [-1, 0], [0, 1], [1, 0]];
const MAX = 200 * 201; // n * m + m
const trapRainWater = (g) => {
    let n = g.length, m = g[0].length;
    if (n == 0) return 0;
    let res = 0, max = Number.MIN_SAFE_INTEGER;
    let pq = new MinPriorityQueue({priority: x => x[0] * MAX + x[1]}); // first priority: x[0], smaller comes first. second priority: x[1], smaller comes first
    let visit = initialize2DArrayNew(n, m);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                pq.enqueue([g[i][j], i * m + j]);
                visit[i][j] = true;
            }
        }
    }
    while (pq.size()) { // BFS
        let cur = pq.dequeue().element;
        let h = cur[0], r = cur[1] / m >> 0, c = cur[1] % m; // height row column
        max = Math.max(max, h);
        for (let k = 0; k < 4; k++) {
            let x = r + dir[k][0], y = c + dir[k][1];
            if (x < 0 || x >= n || y < 0 || y >= m || visit[x][y]) continue;
            visit[x][y] = true;
            if (g[x][y] < max) res += max - g[x][y];
            pq.enqueue([g[x][y], x * m + y]);
        }
    }
    return res;
};

const initialize2DArrayNew = (n, m) => { let data = []; for (let i = 0; i < n; i++) { let tmp = Array(m).fill(false); data.push(tmp); } return data; };
Trapping Rain Water II