#22HardHeap & Breadth-First Search· Min-Heap Flood Fill from the Boundary

Trapping Rain Water II

An `m x n` matrix `heightMap` describes a terrain of unit cells, where `heightMap[i][j]` is the height of the block at row `i`, column `j`. After heavy rain, water settles on top of the blocks. Water can flow between cells that share an edge (not diagonally) and drains away over the outer border of the grid. Return the total volume of water that stays trapped. A cell's water level is the lowest height water would need to rise to before it could escape from that cell to the border; the cell holds `level - height` units (never negative). Border cells never hold water.

Input format

heightMap: m x n matrix of non-negative integers

Output format

Integer: total trapped water volume

Examples

Input: heightMap = [[3, 3, 3], [3, 1, 3], [3, 3, 3]]

Output: 2

The centre cell is surrounded by walls of height 3, so it fills from 1 to 3 and holds 2 units.

Input: heightMap = [[5, 5, 5, 5], [5, 1, 1, 5], [5, 1, 5, 5], [5, 5, 5, 5]]

Output: 12

The three interior cells of height 1 are enclosed by height-5 blocks and each holds 4 units.

Input: heightMap = [[4, 4, 4, 4], [4, 0, 2, 4], [4, 4, 1, 4]]

Output: 2

The cell of height 0 can drain through its neighbour of height 2 and then the border cell of height 1, so it only fills to level 2.

Constraints

1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 10^4

Study first

Stacks, Queues & Monotonic Sequences

#heap
#breadth-first-search
#matrix
#priority-queue