Trapping Rain Water (2D)

Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example

Given [0,1,0,2,1,0,1,3,2,1,2,1] return 6

Use two pointers. The idea is to compare the points of two ends and the volume of trapped water is solely dependent on the shortest point.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) < 3:
            return 0

        cnt = 0
        l, r = 0, len(height) - 1
        l_max, r_max = 0, len(height) - 1

        while l < r:
            if height[l] < height[r]:
                if height[l] < height[l_max]:
                    cnt += (height[l_max] - height[l])
                else:
                    l_max = l
                l += 1
            else:
                if height[r] < height[r_max]:
                    cnt += (height[r_max] - height[r])
                else:
                    r_max = r
                r -= 1

        return cnt

Trapping Rain Water (3D)

Given a 3D elevation map represented by a matrix, calculate the volume of water after the rain.

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

We can do the BFS from outside to inside. (find the neighbor cell which is shorter and calculate the trapped water)

The idea is to push all the border cells in the heap first, every time we pop a cell from the heap which implying the cell is the shortest in the heap. For every cell we pop from heap, we visit all its neighbors. Because we know that the cell is the shortest, if its neighbor is shorter than it, the water will be trapped in its neighbor cell.

class Solution(object):
    def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """
        if not len(heightMap):
            return 0

        m = len(heightMap)
        n = len(heightMap[0])
        heap = []
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        visited = [[False for i in range(n)] for j in range(m)]
        res = 0

        # push all the boarder cells into heap
        for i in range(m):
            if i == 0 or i == m-1:
                for j in range(n):
                    heapq.heappush(heap, (heightMap[i][j], (i,j)))
            else:
                heapq.heappush(heap, (heightMap[i][0], (i,0)))
                heapq.heappush(heap, (heightMap[i][n-1], (i,n-1)))


        while heap:
            cell = heapq.heappop(heap)
            for dir in directions:
                i, j = cell[1][0], cell[1][1]
                x, y = i + dir[0], j + dir[1]

                if 0 < x < m-1 and 0 < y < n-1 and not visited[x][y]:
                    visited[x][y] = True
                    if heightMap[x][y] < heightMap[i][j]:
                        res += heightMap[i][j] - heightMap[x][y]
                        heightMap[x][y] = heightMap[i][j]
                    heapq.heappush(heap, (heightMap[x][y],(x,y)))

        return res