# python solution with heap

• ``````class Solution(object):
def trapRainWater(self, heightMap):
if not heightMap or not heightMap[0]:
return 0

import heapq
m, n = len(heightMap), len(heightMap[0])
heap = []
visited = [[0]*n for _ in xrange(m)]

# Push all the block on the border into heap
for i in xrange(m):
for j in xrange(n):
if i == 0 or j == 0 or i == m-1 or j == n-1:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = 1

result = 0
while heap:
height, i, j = heapq.heappop(heap)
for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
if 0 <= x < m and 0 <= y < n and not visited[x][y]:
result += max(0, height-heightMap[x][y])
heapq.heappush(heap, (max(heightMap[x][y], height), x, y))
visited[x][y] = 1
return result
``````

The idea is that we maintain all the points of the current border in a min heap and always choose the point with the lowest length. This is actually an optimized searching strategy over the trivial brute force method: instead of dfs each point to find the lowest "border" of its connected component, we can always start a search from the lowest border and update the points adjacent to it.

• so interesting a solve

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.