hardHeap / Priority QueuePure DSA~50 min
Reservoir On Elevation Grid
A 2-D elevation map of a facility floor shows wall heights at each cell. After heavy rain, water pools wherever it is surrounded by higher terrain. Compute the total volume of water retained on the whole map.
Problem
Given an m×n matrix of non-negative heights representing a 2-D elevation map, compute how much water it can trap after raining. Water escapes off the grid's outer border.
Input
An m×n matrix heightMap of non-negative integers (1 ≤ m, n ≤ 200, 0 ≤ height ≤ 2·10^4).
Output
An integer: the total trapped water volume.
Constraints
- 1 ≤ m, n ≤ 200
- Water can only be retained by strictly enclosing walls
- Border cells can never hold water
Examples
Example 1
Input
heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output
4
Interior dips hold a combined 4 units bounded by surrounding walls.
Example 2
Input
heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output
10
The bowl traps water up to the height-3 rim.