# Leetcode Trapping Rain Water II problem solution

In this Leetcode Trapping Rain Water II problem solution You are 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.

## Problem solution in Python.

```from heapq import heappush, heappop, heapify

class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
mlen = len(heightMap)
if mlen == 0:
return 0
nlen = len(heightMap[0])
if nlen == 0:
return 0

HEAP = []
visited = [[False for _ in range(nlen)] for _ in range(mlen)]
for i, height in enumerate(heightMap[0]):
HEAP.append(Tile(0, i, height))
visited[0][i] = True
for i, height in enumerate(heightMap[-1]):
HEAP.append(Tile(mlen - 1, i, height))
visited[-1][i] = True
for i in range(mlen):
HEAP.append(Tile(i, 0, heightMap[i][0]))
HEAP.append(Tile(i, nlen - 1, heightMap[i][-1]))
visited[i][0] = True
visited[i][-1] = True
heapify(HEAP)

res = 0
while HEAP:
tile = heappop(HEAP)
m, n, h = tile.m, tile.n, tile.h
if m < mlen - 1 and not visited[m + 1][n]:
visited[m + 1][n] = True
res += max(h - heightMap[m + 1][n], 0)
heappush(HEAP, Tile(m + 1, n, max(h, heightMap[m + 1][n])))

if tile.m > 0 and not visited[m - 1][n]:
visited[m - 1][n] = True
res += max(h - heightMap[m - 1][n], 0)
heappush(HEAP, Tile(m - 1, n, max(h, heightMap[m - 1][n])))

if n < nlen - 1 and not visited[m][n + 1]:
visited[m][n + 1] = True
res += max(h - heightMap[m][n + 1], 0)
heappush(HEAP, Tile(m, n + 1, max(h, heightMap[m][n + 1])))

if n > 0 and not visited[m][n - 1]:
visited[m][n - 1] = True
res += max(h - heightMap[m][n - 1], 0)
heappush(HEAP, Tile(m, n - 1, max(h, heightMap[m][n - 1])))
return res

class Tile:
def __init__(self, m, n, h):
self.m = m
self.n = n
self.h = h

def __lt__(self, other):
if self.h < other.h:
return True
elif self.h > other.h:
return False
else:
if self.m < other.m:
return True
elif self.m > other.m:
return False
else:
return self.n < other.n
```

## Problem solution in Java.

```class Solution {

class Coordinates{
int row;
int col;

public Coordinates(int r, int c){
this.row = r;
this.col = c;
}

}

int[] top =    {0, 0, 1, -1};
int[] bottom = {1,-1, 0, 0};

public int trapRainWater(int[][] heightMap) {
int m = heightMap.length;
int n = heightMap[0].length;

boolean [][] visited = new boolean[m][n];

PriorityQueue<Coordinates> pq = new PriorityQueue<Coordinates>(
(a,b) -> heightMap[a.row][a.col] - heightMap[b.row][b.col]);

int water = 0;
pushToQueue(pq, heightMap, visited, m, n);
int max = Integer.MIN_VALUE;

while(pq.size()>0)
{
Coordinates element = pq.poll();
int x = element.row;
int y = element.col;
int val = heightMap[x][y];

max = Math.max(max, val);

for(int i=0;i<4;i++)
{
int t = x + top[i];
int b = y + bottom[i];

if(t<0 || t>=m || b<0 || b>=n || visited[t][b])
continue;
pq.offer(new Coordinates(t,b));
visited[t][b] = true;
}

if(heightMap[x][y] < max)
water += max - heightMap[x][y];
}
return water;
}

void pushToQueue(PriorityQueue<Coordinates> pq, int [][]heightMap,
boolean[][] visited,int m, int 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.offer(new Coordinates(i,j));
visited[i][j] = true;
}
}
}
}

}
```

## Problem solution in C++.

```class Solution {

public:

int minaround(int i, int j, vector<vector<int>>& water){
int n = water.size();
int m = water[0].size();
int min_num = water[i][j];
if(i-1>=0)
min_num = min(min_num,water[i-1][j]);
if(j-1>=0)
min_num = min(min_num,water[i][j-1]);
if(i+1<n)
min_num = min(min_num,water[i+1][j]);
if(j+1<m)
min_num = min(min_num,water[i][j+1]);
if(i==n-1||i==0||j==m-1||j==0) min_num=0;

return min_num;

}

void flowout(int i, int j, vector<vector<int>> &water, vector<vector<int>>& heightMap){

if(i<0||j<0) return;
int n = heightMap.size();
int m = heightMap[0].size();
if(i>=n||j>=m) return;
int level = max(minaround(i,j,water),heightMap[i][j]);
if(level<water[i][j]){
water[i][j] = level;
flowout(i,j+1,water,heightMap);
flowout(i,j-1,water,heightMap);
flowout(i+1,j,water,heightMap);
flowout(i-1,j,water,heightMap);
}
return;
}
int trapRainWater(vector<vector<int>>& heightMap) {

int n = heightMap.size();
int m = heightMap[0].size();

vector<vector<int>> water(n,vector<int>(m,20000));
for(int i =0;i<n;i++){
for(int j =0;j<m;j++){
flowout(i,j,water,heightMap);
}
}
int ans = 0;
for(int i =0;i<n;i++){
for(int j =0;j<m;j++){
ans = ans + water[i][j] - heightMap[i][j];
}
}

return ans;
}
};
```