Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/407.html

407. Trapping Rain Water II

Level

Hard

Description

Given an m x n matrix 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:

Both m and n are 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.

Image text

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.

Image text

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

Solution

If height has length 0, then return 0.

Use priority queue and breadth first search. For each cell, store its row, column and height.

Initially, offer all the cells on the border to the priority queue, where the cell with the minimum height is polled first.

Each time a cell is polled from the priority queue, consider its adjacent cells. If an adjacent cell has a smaller height, then the adjacent cell will have water trapped, so obtain the amount of water in the adjacent cell which is the difference in height, add the amount of water in the adjacent cell to the result, and offer the adjacent cell to the priority queue with the height of the adjacent cell as the height of the current cell.

If an adjacent cell has a larger height, then the adjacent cell won’t have water contained, so just offer the adjacent cell to the priority queue, using the height of the adjacent cell.

Finally, return the total amount of water trapped.

  • class Solution {
        public int trapRainWater(int[][] heightMap) {
            if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0)
                return 0;
            int rows = heightMap.length, columns = heightMap[0].length;
            boolean[][] visited = new boolean[rows][columns];
            PriorityQueue<Cell> priorityQueue = new PriorityQueue<Cell>();
    
            // top/bottom border process
            for (int i = 0; i < columns; i++) {
                visited[0][i] = true;
                visited[rows - 1][i] = true;
                priorityQueue.offer(new Cell(0, i, heightMap[0][i]));
                priorityQueue.offer(new Cell(rows - 1, i, heightMap[rows - 1][i]));
            }
    
            // left/right border process
            for (int i = 1; i < rows - 1; i++) {
                visited[i][0] = true;
                visited[i][columns - 1] = true;
                priorityQueue.offer(new Cell(i, 0, heightMap[i][0]));
                priorityQueue.offer(new Cell(i, columns - 1, heightMap[i][columns - 1]));
            }
            int amount = 0;
            int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
            while (!priorityQueue.isEmpty()) {
                while (!priorityQueue.isEmpty()) { // 第一次poll出来的,是整个3D地图的4个border上的最低点
                int row = cell.row, column = cell.column, height = cell.height;
                for (int[] direction : directions) {
                    int newRow = row + direction[0], newColumn = column + direction[1];
                    if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) {
                        if (!visited[newRow][newColumn]) {
                            visited[newRow][newColumn] = true;
                            int newCellHeight = heightMap[newRow][newColumn];
                            if (height > newCellHeight) { // always enque with higher height
                                amount += height - newCellHeight;
                                priorityQueue.offer(new Cell(newRow, newColumn, height));
                            } else
                                priorityQueue.offer(new Cell(newRow, newColumn, newCellHeight));
                        }
                    }
                }
            }
            return amount;
        }
    }
    
    class Cell implements Comparable<Cell> {
        int row;
        int column;
        int height;
    
        public Cell(int row, int column, int height) {
            this.row = row;
            this.column = column;
            this.height = height;
        }
    
        public int compareTo(Cell cell2) {
            return this.height - cell2.height;
        }
    }
    
  • // OJ: https://leetcode.com/problems/trapping-rain-water-ii/
    // Time: O(MNlog(MN))
    // Space: O(MN)
    // Ref: https://discuss.leetcode.com/topic/60914/concise-c-priority_queue-solution
    class Solution {
        typedef array<int, 3> Point;
    public:
        int trapRainWater(vector<vector<int>>& A) {
            int M = A.size(), N = A[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = 0, maxH = INT_MIN;
            priority_queue<Point, vector<Point>, greater<>> pq;
            vector<vector<bool>> seen(M, vector<bool>(N));
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (i == 0 || i == M - 1 || j == 0 || j == N - 1) {
                        pq.push({ A[i][j], i, j });
                        seen[i][j] = true;
                    }
                }
            }
            while (pq.size()) {
                auto [h, x, y] = pq.top();
                pq.pop();
                maxH = max(maxH, h);
                for (auto &[dx, dy] : dirs) {
                    int a = x + dx, b = y + dy;
                    if (a < 0 || a >= M || b < 0 || b >= N || seen[a][b]) continue;
                    seen[a][b] = true;
                    if (A[a][b] < maxH) ans += maxH - A[a][b];
                    pq.push({ A[a][b], a, b });
                }
            }
            return ans;
        }
    };
    
  • '''
    >>> from itertools import pairwise
    >>> dirs = (-1, 0, 1, 0, -1)
    >>> pairwise(dirs)
    <itertools.pairwise object at 0x104dbe470>
    >>> list(pairwise(dirs))
    [(-1, 0), (0, 1), (1, 0), (0, -1)]
    '''
    
    class Solution:
        def trapRainWater(self, heightMap: List[List[int]]) -> int:
            m, n = len(heightMap), len(heightMap[0])
            vis = [[False] * n for _ in range(m)]
            pq = []
            for i in range(m):
                for j in range(n):
                    if i == 0 or i == m - 1 or j == 0 or j == n - 1: # border enqueue
                        heappush(pq, (heightMap[i][j], i, j)) # default order
                        vis[i][j] = True
            ans = 0
            dirs = (-1, 0, 1, 0, -1)
            while pq:
                h, i, j = heappop(pq)
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if x >= 0 and x < m and y >= 0 and y < n and not vis[x][y]:
                        ans += max(0, h - heightMap[x][y]) # look for neighbour which is lower than pop result hight
                        vis[x][y] = True
                        heappush(pq, (max(h, heightMap[x][y]), x, y))
            return ans
    
    ############
    
    class Solution(object):
      def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """
        if not heightMap:
          return 0
        h = len(heightMap)
        w = len(heightMap[0])
        ans = 0
        heap = []
        visited = set()
        for j in range(w):
          heapq.heappush(heap, (heightMap[0][j], 0, j))
          heapq.heappush(heap, (heightMap[h - 1][j], h - 1, j))
          visited |= {(0, j), (h - 1, j)}
        for i in range(h):
          heapq.heappush(heap, (heightMap[i][0], i, 0))
          heapq.heappush(heap, (heightMap[i][w - 1], i, w - 1))
          visited |= {(i, 0), (i, w - 1)}
        dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        while heap:
          height, i, j = heapq.heappop(heap)
          for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and (ni, nj) not in visited:
              ans += max(0, height - heightMap[ni][nj])
              heapq.heappush(heap, (max(heightMap[ni][nj], height), ni, nj))
              visited |= {(ni, nj)}
        return ans
    
    
  • func trapRainWater(heightMap [][]int) (ans int) {
    	m, n := len(heightMap), len(heightMap[0])
    	pq := hp{}
    	vis := make([][]bool, m)
    	for i, row := range heightMap {
    		vis[i] = make([]bool, n)
    		for j, v := range row {
    			if i == 0 || i == m-1 || j == 0 || j == n-1 {
    				heap.Push(&pq, tuple{v, i, j})
    				vis[i][j] = true
    			}
    		}
    	}
    	dirs := []int{-1, 0, 1, 0, -1}
    	for len(pq) > 0 {
    		p := heap.Pop(&pq).(tuple)
    		for k := 0; k < 4; k++ {
    			x, y := p.i+dirs[k], p.j+dirs[k+1]
    			if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] {
    				ans += max(0, p.v-heightMap[x][y])
    				vis[x][y] = true
    				heap.Push(&pq, tuple{max(p.v, heightMap[x][y]), x, y})
    			}
    		}
    	}
    	return
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    type tuple struct{ v, i, j int }
    type hp []tuple
    
    func (h hp) Len() int            { return len(h) }
    func (h hp) Less(i, j int) bool  { return h[i].v < h[j].v }
    func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
    func (h *hp) Push(v interface{}) { *h = append(*h, v.(tuple)) }
    func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
    

All Problems

All Solutions