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;
    }
}

All Problems

All Solutions