# 407. Trapping Rain Water II
###### tags: `Heap`, `Bloomberg`

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:**

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.

Solution:
[visualization video](https://www.youtube.com/watch?v=cJayBq38VYw)

class Solution {
    private static int[] dx = new int[]{0, 1, 0, -1};
    private static int[] dy = new int[]{1, 0, -1, 0};
    
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null) return 0;
        int m = heightMap.length;
        int n = heightMap[0].length;
        if (m <= 2 || n <= 2) return 0;
        
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        int max = 0;
        int total = 0;
        
        for (int i = 0; i < m; i++) {
            addGrid(i, 0, pq, heightMap, visited);
            addGrid(i, n - 1, pq, heightMap, visited);
        }
        for (int i = 1; i < n - 1; i++) {
            addGrid(0, i, pq, heightMap, visited);
            addGrid(m - 1, i, pq, heightMap, visited);
        }
        
        while (!pq.isEmpty()) {
            int[] grid = pq.poll();
            max = Math.max(max, grid[0]);
            for (int i = 0; i < 4; i++) {
                int nx = grid[1] + dx[i];
                int ny = grid[2] + dy[i];
                if (isInBoundary(nx, ny, heightMap) && !visited[nx][ny]) {
                    if (heightMap[nx][ny] < max) {
                        total += max - heightMap[nx][ny];
                    }
                    addGrid(nx, ny, pq, heightMap, visited);
                }
            }
        }
        
        return total;
    }
    
    private void addGrid(int x, int y, PriorityQueue<int[]> pq, int[][] heightMap, boolean[][] visited) {
        int[] grid = new int[3];
        grid[0] = heightMap[x][y];
        grid[1] = x;
        grid[2] = y;
        pq.add(grid);
        visited[x][y] = true;
    }
    
    private boolean isInBoundary(int x, int y, int[][] map) {
        if (x < 0 || x >= map.length) return false;
        if (y < 0 || y >= map[0].length) return false;
        return true;
    }
}

class Wall {
    int h;
    int x;
    int y;
}

[1,4,3,1,3,2]
[3,2,1,3,2,4]
[2,3,3,2,3,1]

[o,o,o,o,o,o]
[o,o,o,o,o,o]
[o,o,o,o,o,o]

pq: [3,3,3,3,4,4]
curr = 3;
max = 3;

total = 4

public int trapRainWater(int[][] heightMap) {
    int[] dx = new int{0, 1, 0, -1};
    int[] dy = new int{1, 0, -1, 0};

    int m = heightMap.length;
    int n = heightMap[0].length;
    boolean[][] visited = new boolean[m][n];
    PriorityQueue<int[]> pq = new LinkedList((a, b) -> a[2] - b[2]);
    int max = 0;
    int trapped = 0;
    for (int i = 0; i < m; i++) {
        addGrid(i, 0, pq, visited, heightMap);
        addGrid(i, n - 1, pq, visited, heightMap);
    }
    for (int i = 1; i < n - 1; i++) {
        addGrid(0, i, pq, visited, heightMap);
        addGrid(m - 1, i, pq, visited, heightMap);
    }
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        max = Math.max(max, curr);
        
        for (int i = 0; i < 4; i++) {
            int nx = curr[0] + dx[i];
            int ny = curr[1] + dy[i];
            if (isInBoundary(nx, ny, m, n) && !visited[nx][ny]) {
                if (heightMap[nx][ny] < max) {
                    trapped += max - heightMap[nx][ny];
                }
                addGrid(nx, ny, pq, visited, heightMap);
            }
        }
    }
    return trapped;
}

private void addGrid(int x, int y, PriorityQueue<int[]> pq, boolean[][] visited, int[][] heightMap) {
    visited[x][y] = true;
    int[] wall = new int[]{x, y, heightMap[x][y]}
    pq.offer(wall);
}

private boolean isInBoundary(int x, int y, int m, int n) {
    return 0 <= x && x < m && 0 <= y &&  y < n
}