407.Trapping Rain Water II

Tags: [heap], [min_heap], [DFS], [backtracking], [matrix], [graph]

Com: {g}

Link: https://leetcode.com/problems/trapping-rain-water-ii/\#/description

Given anm x nmatrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:
Bothmandnare less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

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.

The above image represents the elevation map[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]before the rain.
After the rain, water are trapped between the blocks. The total volume of water trapped is 4.

Solution: Heap, Min Heap

import heapq

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

        num_of_rows = len(heightMap)
        num_of_cols = len(heightMap[0])

        visited = [[False for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        min_heap = []

        # put borders into the min heap
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if row == 0 or row == num_of_rows - 1 or\
                   col == 0 or col == num_of_cols - 1:
                    min_heap.append((heightMap[row][col], row, col))
                    visited[row][col] = True

        heapq.heapify(min_heap)

        amount = 0
        while min_heap:
            h, row, col = heapq.heappop(min_heap)

            # iterate four directions
            # top, left, bottom, right
            directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
            for d in directions:
                r, c = row + d[0], col + d[1]
                if 0 <= r < num_of_rows and 0 <= c < num_of_cols and not visited[r][c]:
                    if heightMap[r][c] < h:
                        amount += h - heightMap[r][c]
                        heightMap[r][c] = h

                    heapq.heappush(min_heap, (heightMap[r][c], r, c))
                    visited[r][c] = True

        return amount

Revelation:

• We first put all the borders into the min heap, then start searching from the shortest border, after fill the water, then put the 'new border' into the min heap. The reason this strategy is correct is that think about we just put all 'real' borders into the min heap, then pop up the shortest border, we iterate its four neighbors, if we can find one cell whose height is less than the current border's height, then we can fill the water, because the current popped up border is the shortest border, if we find one height is less than this shortest boarder, that means this height is less than all borders, so this guarantees we can fill the water here. And after filling the water, the current filled water cell become one new 'border'.

Note:

• Time complexity = O(2 * num__of__rows + 2 * num__of__cols + nlgn), n is the total number of elements of the heightMap.
• Time complexity of heapify = O(m), m is the number of elements in heap.
• Time complexity of heap pop = O(lgm), m is the number of elements in heap.
• Time complexity of heap push = O(lgm), m is the number of elements in heap.

Time Limited Exceeded: DFS, Backtracking

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

        num_of_rows = len(heightMap)
        num_of_cols = len(heightMap[0])

        amount = 0

        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                visited = [[False for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
                if self.dfs(heightMap, num_of_rows, num_of_cols, heightMap[row][col], row, col, visited):
                    max_water_height = self.get_max_water_height(heightMap, num_of_rows, num_of_cols, visited)    
                    amount += self.fill_water(heightMap, num_of_rows, num_of_cols, max_water_height, visited)

        return amount

    def dfs(self, h_map, num_of_rows, num_of_cols, bottom_line_height, row, col, visited):
        # base case
        if row == 0 or row == num_of_rows - 1 or col == 0 or col == num_of_cols - 1:
            return False

        visited[row][col] = True

        # iterate four directions:
        # top, left, bottom, right
        directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
        for d in directions:
            r, c = row + d[0], col + d[1]
            if 0 <= r < num_of_rows and 0 <= c < num_of_cols and\
               h_map[r][c] <= bottom_line_height and not visited[r][c]:
                if not self.dfs(h_map, num_of_rows, num_of_cols, bottom_line_height, r, c, visited):
                    return False

        return True

    def get_max_water_height(self, h_map, num_of_rows, num_of_cols, visited):
        # get the min height of the surroundings.
        min_surrounding_h = sys.maxint

        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if not visited[row][col]:
                    continue

                # iterate four directions
                # top, left, bottom, right
                directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
                for d in directions:
                    r, c = row + d[0], col + d[1]
                    if 0 <= r < num_of_rows and 0 <= c < num_of_cols and not visited[r][c]:
                        min_surrounding_h = min(min_surrounding_h, h_map[r][c])

        return min_surrounding_h

    def fill_water(self, h_map, num_of_rows, num_of_cols, max_water_height, visited):
        amount = 0

        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if not visited[row][col]:
                    continue

                amount += max_water_height - h_map[row][col]
                h_map[row][col] = max_water_height

        return amount

Revelation:

• Each DFS need a new visited map.

Note:

• Time complexity = O(n^2), n is the total number of elements in heightMap.