Rainwater on a Terrain Map
A terrain is described by heightMap, a grid where each cell holds the height of a 1x1 column. After heavy rain, water collects in dips and can flow out only through the outer border of the map (water moves horizontally or vertically, never diagonally).
Return the total volume of water that stays trapped on the terrain.
Example 1
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] Output: 4
Example 2
Input: heightMap = [[5,5,5],[5,1,5],[5,5,5]] Output: 4
Constraints
- 0 <= rows, cols <= 200
- 0 <= heightMap[i][j] <= 2 * 10^4
Hint 1
The border cells form the initial wall. Water level inside is limited by the lowest point of the wall around it.
Hint 2
Use a min-heap of boundary cells: repeatedly pop the lowest, flood its unvisited neighbours, and push them with height max(own, current level).
Discussion 0
Join free to post in the discussion.
Good practice for: Game Developer, Data Scientist, Backend Developer, Machine Learning Engineer, Embedded Systems Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.