Compute rainwater accumulation on a height grid

Problem Statement

Given an m x n integer matrix height_map representing the elevation of each unit cell on a terrain, calculate the total volume of rainwater trapped on the terrain after rainfall.

Water can flow to neighboring cells in four directions (up, down, left, right). Water at the outer boundary of the grid immediately spills off the edges and cannot be contained.

Function Signature

def trap_rain_water(height_map: list[list[int]]) -> int:
    pass

Input & Output Format

• Input: height_map, a 2D list of integers where height_map[r][c] is the height of cell (r, c).
• Output: An integer representing the total units of water retained across all cells.

Constraints

• m == len(height_map)
• n == len(height_map[i])
• 1 <= m, n <= 200
• 0 <= height_map[r][c] <= 20000

Examples

Example 1

Input: height_map = [
  [1, 4, 3, 1, 3, 2],
  [3, 2, 1, 3, 2, 4],
  [2, 3, 3, 2, 3, 1]
]
Output: 4
Explanation:
Cell (1, 1) has height 2 and can hold 1 unit of water.
Cell (1, 2) has height 1 and can hold 2 units of water.
Cell (1, 4) has height 2 and can hold 1 unit of water.
Total water trapped = 1 + 2 + 1 = 4.

Example 2

Input: height_map = [
  [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

Edge Cases

• Grids with m < 3 or n < 3 cannot trap any water because every cell is on the boundary. The answer should be 0.
• Flat terrains where all heights are equal should return 0.
• Monotonically increasing or decreasing elevation profiles should return 0.