Trapping Rain Water II

Problem Id: 407 Difficulty: Hard


Intuition

Solution


class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        h = len(heightMap)
        if h <= 2:
            return 0
        w = len(heightMap[0])
        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][0], i, 0
            ))
            heapq.heappush(min_height_lookup, (
                heightMap[i][w - 1], i, w - 1
            ))
            visited[i][0] = visited[i][w - 1] = True

        for j in range(1, w - 1):
            heapq.heappush(
                min_height_lookup,
                (heightMap[0][j], 0, j)
            )
            heapq.heappush(
                min_height_lookup,
                (heightMap[h-1][j], h-1, j)
            )
            visited[0][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