571. Rain Pools in 3D
A survey team has a rectangular height map of a landscape: heights[r][c] is the ground height of the square cell at row r, column c. A heavy rain falls and water settles on the cells. Water can flow between cells that share a side (up, down, left, right) and can only move into a neighbour whose water surface is not higher than the current surface. Any water that reaches a cell on the outer border of the map flows off the map and is lost.
Return the total volume of water that remains trapped on the map once everything has settled, where a cell holding water up to surface level L over ground height h contributes L - h. Maps with fewer than three rows or fewer than three columns can hold nothing.
The result always fits in a 32-bit signed integer. Aim for O(m n log(m n)) time and O(m n) space.
Example 1
- Input:
- heights = [[6,6,6,6],[6,2,3,6],[6,4,1,6],[6,6,6,6]]
- Output:
- 14
- Explanation:
The four inner cells are enclosed by a rim of height 6, so they fill to 6: 4 + 3 + 2 + 5 = 14.
Example 2
- Input:
- heights = [[5,5,5,5],[5,1,2,5],[5,2,1,3],[5,5,5,5]]
- Output:
- 6
- Explanation:
The lowest exit on the rim is the border cell of height 3, so all four inner cells fill to level 3: 2 + 1 + 1 + 2 = 6.
Example 3
- Input:
- heights = [[3,0,3,0,3]]
- Output:
- 0
- Explanation:
With a single row every cell is on the border, so no water stays.
Constraints
1 ≤ m, n ≤ 500wherem = heights.lengthandn = heights[0].length0 ≤ heights[r][c] ≤ 5000- All rows have the same length.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(m n log(m n))
- Space
- O(m n)