# Trapping Rain Water II  ## Solution

``````
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
h = len(heightMap)
if h <= 2:
return 0
w = len(heightMap)
if w <= 2:
return 0

# Using heap and bread first search
visited = [[False] * w for _ in range(h)]
water = 0
min_height_lookup = []

# Init boundary
for i in range(h):
heapq.heappush(min_height_lookup, (
heightMap[i], i, 0
))
heapq.heappush(min_height_lookup, (
heightMap[i][w - 1], i, w - 1
))
visited[i] = visited[i][w - 1] = True

for j in range(1, w - 1):
heapq.heappush(
min_height_lookup,
(heightMap[j], 0, j)
)
heapq.heappush(
min_height_lookup,
(heightMap[h-1][j], h-1, j)
)
visited[j] = visited[h - 1][j] = True

# Bread first search
while min_height_lookup:
height, i, j = heapq.heappop(min_height_lookup)
for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
if x < 0 or y < 0 or x >= h or y >= w:
continue
if visited[x][y]:
continue
water += max(0, height - heightMap[x][y])
visited[x][y] = True
heapq.heappush(
min_height_lookup,
(max(height, heightMap[x][y]), x, y)
)
return water

``````