0407. Trapping Rain Water II

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

Description

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Example 1:

**Input:** heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
**Output:** 4
**Explanation:** After the rain, water is trapped between the blocks.
We have two small pounds 1 and 3 units trapped.
The total volume of water trapped is 4.

Example 2:

**Input:** heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
**Output:** 10

Constraints:

• m == heightMap.length

• n == heightMap[i].length

• 1 <= m, n <= 200

• 0 <= heightMap[i][j] <= 2 * 104

ac

class Solution {
    public int trapRainWater(int[][] heightMap) {
        // edge cases
        if (heightMap.length <= 2 || heightMap[0].length <= 2) return 0;

        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0}, {-1,0}};
        int row = heightMap.length, col = heightMap[0].length;
        boolean[][] visited = new boolean[row][col];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {return heightMap[a[0]][a[1]] - heightMap[b[0]][b[1]];});
        // priority queue, get smallest. start from boarder
        for (int c = 0; c < col; c++) {
            pq.offer(new int[]{0, c}); visited[0][c] = true;
            pq.offer(new int[]{row-1, c}); visited[row-1][c] = true;
        }
        for (int r = 1; r < row-1; r++) {
            pq.offer(new int[]{r, 0}); visited[r][0] = true;
            pq.offer(new int[]{r, col-1});visited[r][col-1] = true;
        }

        // each time process smallest one
        int sum = 0;
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int min = heightMap[curr[0]][curr[1]];
            Queue<int[]> q = new LinkedList<>();
            q.offer(curr);
            while (!q.isEmpty()) {
                int[] curr2 = q.poll();

                // 4 directions
                for (int[] d : dirs) {
                    int r = curr2[0] + d[0];
                    int c = curr2[1] + d[1];
                    if (r < 0 || r >= row || c < 0 || c >= col || visited[r][c]) continue; // out of boundary or visited
                    if (heightMap[r][c] <= min) { // add to sum, add to queue
                        sum += min - heightMap[r][c];
                        q.offer(new int[]{r, c});
                    } else { // greater one, add to pq
                        pq.offer(new int[]{r, c});
                    }
                    visited[r][c] = true; // marked visited
                }
            }
        }

        return sum;
    }
}

/*
The idea is same with https://leetcode.com/problems/trapping-rain-water/description/
just fron 2D to 3D
start from the edge, move smallest inward, when meet smaller one add to sum
visualization: https://www.youtube.com/watch?v=cJayBq38VYw

1) priority queue, start from boarder. 2) poll smallest one, queue BFS, when meet smaller add to sum / add to queue for next, when meet bigger add to priority queue.
*/