Trapping Rain Water II
Hard · Heap & Counting · Array · Breadth-First Search · Heap (Priority Queue) · Matrix
Problem
You are given an m x n grid heightMap: each cell is a square column of the given height, forming a landscape seen from above.
Rain falls everywhere. Water can flow between cells that share a side, and it can run off the map over the outer edge. Return the total volume of water that stays trapped once everything has settled (each unit of height over one cell is one unit of volume).
Examples
Input: heightMap = [[3,3,3],[3,1,3],[3,3,3]] Output: 2
The center is surrounded by height 3, so it fills from 1 to 3: 2 units.
Input: heightMap = [[5,5,5,5],[5,1,2,5],[5,4,5,5]] Output: 5
Water escapes over the border cell of height 4, so the pool stands at 4: 3 units over the 1 and 2 over the 2.
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] Output: 4
The inner cells of height 2 and 1 on the left fill to 3 (1 + 2 units), and the inner 2 on the right, cut off by a 3, fills to 3 as well (1 unit): 4 in all.
Constraints
- m == len(heightMap), n == len(heightMap[i])
- 1 <= m, n <= 200
- 0 <= heightMap[i][j] <= 2 · 10^4
Approaches
- Baseline: lower the water levels until they settle — time O((m · n)²) worst case, space O(m · n)
Follow-up
The same heap walk gives more than the total: each cell's final level is the value it is pushed with. That level is the lowest possible "highest point" on any path from the cell to the edge, a minimax path, which is why a Dijkstra-style search finds it.
Related problems
Start free on Cariara · Coding problems · System design studio
