Rain Pools on a Relief Map

Hard

The terrain is given by an m × n table heights, where heights[i][j] is the height of a cell. A heavy rain has fallen. Water flows between cells that share a side and drains off the map over its edges, so no water stays above the cells on the border of the table. Return the total volume of water left on the map: the sum, over all cells, of the water level above a cell minus the cell's height.

Example 1

heights=[[4, 4, 4, 4], [4, 1, 2, 4], [4, 4, 3, 4]] → 3

The lowest point of the rim is the cell of height 3 in the bottom row, so the water rises to level 3: 2 units above the cell of height 1 and 1 more above the cell of height 2. That is 3 in total.

Example 2

heights=[[2, 2, 2], [2, 0, 1], [2, 2, 2]] → 1

The pit at height 0 borders an edge cell of height 1, and the water drains over it. 1 unit stays.

Example 3

heights=[[5, 3, 5]] → 0

Every cell is on the edge of the map, so nothing can hold water.

Constraints

1 ≤ m, n ≤ 200
0 ≤ heights[i][j] ≤ 2·10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Matrix Heap (Priority Queue)

Similar problems

Ball Into the Hole Hard Trim the Bushes, Shortest First Hard Crossing at High Tide Hard A Crate in the Warehouse Hard Repaint Arrows to Reach the Exit Hard

Input

heights=[[4, 4, 4, 4], [4, 1, 2, 4], [4, 4, 3, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.