335. Trapping Rain Water II
A plot of terrain is modeled as an m × n grid of unit columns: heightMap[r][c] is the elevation of the column at row r, column c. It rains until every basin is full.
Water on a cell can flow to any of its 4 edge-adjacent neighbors whenever the water surface there would sit lower, and anything that reaches the border of the grid drains away off the edge. So water only stays where it is completely walled in by taller terrain.
Return the total volume of standing water after everything settles, as a single integer. Border cells can never hold water, and a grid thinner than 3 cells in either direction traps nothing at all.
Example 1:
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: The middle row has a basin: the cells of height 2, 1 and 2 at positions (1,1), (1,2) and (1,4) are ringed by walls of height ≥ 3, so water rises to level 3 above them: (3−2) + (3−1) + (3−2) = 4.
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
Explanation: A square bowl: the ring of 3s traps water at level 3 over the whole interior. Eight cells of height 2 hold 1 unit each and the center cell of height 1 holds 2, for a total of 10.
Constraints:
- 1 ≤ m, n ≤ 200
- 0 ≤ heightMap[r][c] ≤ 2 × 10⁴
Hints:
In the 1-D version you scan from both ends because water leaks over the lower of two side walls. In 2-D, water can leak in any of four directions — the relevant 'wall' is the entire boundary between a cell and the outside world.
Work from the outside in. The lowest cell anywhere on the current boundary is the weakest point of the dam: nothing inside can hold water above that level without leaking through it. Process boundary cells lowest-first with a min-heap.
When you pop a cell at water level L and step to an unvisited neighbor of ground height h, the neighbor holds max(0, L − h) water and joins the frontier at level max(L, h). Every cell enters the heap exactly once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Expected output: 4