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

407.trapping-rain-water-ii-1.py

# https://github.com/WillWang-X/leetcode-with-illustrations/blob/master/407.trapping-rain-water-ii.ipynb
# https://kyso.io/will/407-trapping-rain-water-ii
'''
Solution1: queue and do like siege(queue by layers and layers)
Solution2: priority queue and do like flooding (the water level rises gradually)
'''

# Time: O(n^2)
# Space: O(n^2)

from collections import deque

'''
Q&A:
Why queue?
Everytime we update a new element and it will have a effect on the elements around it. So we need to put it into the queue.
e.g. 
1,2,3,3,5
1,1,2,【2】,4  
1,2,3,3,3
'''

class Solution1(object):
    def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """
        # 0. init: m,n,peakMap,queue
        m = len(heightMap)
        n = len(heightMap[0]) if m else 0
        peakMap = [[0x7FFFFFFF] * n for _ in range(m)]
        queue = deque([])
        
        # 1. put the outer into the queue 
        for i in range(m):
            for j in range(n):
                if i in (0, m-1) or j in (0, n-1):
                    peakMap[i][j] = heightMap[i][j]
                    queue.append((i,j))
                    
        # 2. interate the queue and compare 
        while queue:
            x, y = queue.popleft()
            for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx <= m - 1 and 0 <= ny <= n-1:
                    limit = max(peakMap[x][y], heightMap[nx][ny])
                    if peakMap[nx][ny] > limit:
                        peakMap[nx][ny] = limit 
                        queue.append((nx, ny))
                    
        # 3. result: peakMap - heightMap
        return sum(peakMap[x][y] - heightMap[x][y] for x in range(m) for y in range(n))
    

407.trapping-rain-water-ii-2.py

# Time: O(n^2log(n^2))
# Space: O(1)

from heapq import heappush, heappop
'''
Q&A:
1. Correctness?
We just need to undate the element once cause we make sure that we had already iterate all smaller elements outside
'''

class Solution2(object):
    def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """ 
        # 0. init: m,n, is_visited, heap
        m = len(heightMap)
        n = len(heightMap[0]) if m else 0
        is_visited = [[False] * n for _ in range(m)]
        heap = []
        
        # 1. put the outer into the heap 
        for i in range(m):
            for j in range(n):
                if i in (0, m-1) or j in (0,n-1):
                    heappush(heap, [heightMap[i][j], i, j])
                    is_visited[i][j] = True 
                
        # 2. interate the heap 
        water = 0
        while heap:
            height, x, y = heappop(heap)
            for dx, dy in [(0,1), (0,-1), (-1, 0), (1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx <= m -1 and 0 <= ny <= n-1 and not is_visited[nx][ny]:
                    water += max(0, height - heightMap[nx][ny])
                    heappush(heap, [max(height, heightMap[nx][ny]), nx, ny])
                    is_visited[nx][ny] = True 
        
        return water