Water Held by the Land
heights is a map of a piece of land: heights[r][c] is how high the ground is in that cell. It rains until the land can hold no more. Water flows between cells that share a side, and it runs off over the edge of the map.
Return how much water stays on the land, where one unit covers one cell one step deep.
Example 1
heights [[3,3,3],[3,1,3],[3,3,3]]
returns 2
The middle cell is a hollow of depth 2 with ground of height 3 all around.
Example 2
heights [[5,5,5,5],[5,2,4,5],[5,5,1,5]]
returns 2
The hollow of height 2 fills up to 4. Then the water spills over the cell of height 4 and out past the edge cell of height 1.
Example 3
heights [[1,2,3],[4,5,6]]
returns 0
Every cell is on the edge, so everything runs off.
Constraints
1 <= len(heights) <= 12and1 <= len(heights[0]) <= 120 <= heights[r][c] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Grids problems
- Column TotalsBeginner
- Count Negatives in a Sorted GridBeginner
- Cross TotalBeginner
- Enlarge the PictureBeginner
- Frame TotalBeginner
- Heaviest RowBeginner
- Layer LabelsBeginner
- Mirror the RowsBeginner