python solution with heap

  • 12
    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.

  • 0

    so interesting a solve

Log in to reply

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