Rainwater on Terrain
Problem
A terrain model is given as a grid heights, where heights[r][c] is the elevation of a 1 × 1 column of land. After heavy rain, water collects on top of columns wherever it is enclosed; water flows off the grid through the outer border, and flows freely between cells sharing an edge (not diagonally).
Return the total volume of water trapped on the terrain.
Example 1
- Input:
- heights = [[3, 3, 3, 3], [3, 1, 0, 3], [3, 3, 3, 3]]
- Output:
- 5
The two inner cells are walled in at height 3: they hold 3 - 1 = 2 and 3 - 0 = 3.
Example 2
- Input:
- heights = [[1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1]]
- Output:
- 4
Cell (1,1) holds 1, cell (1,2) holds 2 and cell (1,4) holds 1.
Example 3
- Input:
- heights = [[5, 5, 5], [5, 9, 5], [5, 5, 5]]
- Output:
- 0
Constraints
- 1 ≤ rows, cols ≤ 200
- 0 ≤ heights[r][c] ≤ 2·10^4
Hint
Show the first hint
Water in a cell can rise only as high as the lowest 'wall' between it and the border. The border itself traps nothing.
Walkthrough
How to approach it
01Clarify before coding
- Does water escape diagonally? No, only through edge-adjacent cells.
- Do border cells hold water? No, water flows off the grid from them.
- Can the grid be a single row or column? Yes; then everything is border and the answer is 0.
02Brute force
For each cell, find the minimum over all paths to the border of the maximum height on the path (its water level), e.g. by repeatedly relaxing level[c] = max(height[c], min(level of neighbours)) until nothing changes.
Cost: Each relaxation sweep is O(R·C) and it may need O(R·C) sweeps: O((R·C)²) = 1.6·10^9 for 200 × 200.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.