Show problems as
Classic problem #407HardArrayBreadth-First SearchHeap (Priority Queue)Matrix

Trapping Rain Water II

Real-world version: Water Held by a Moulded Tray
Tracked in this browser only
Read Trapping Rain Water II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tray is moulded from square cells whose wall heights are given as heightMap. Water is poured over the whole tray until it settles.

Water spreads between cells that share a side, and any water reaching the outside edge of the tray runs off. A cell holds water up to the level the surrounding walls can keep in, and never below its own height.

Return the total volume of water the tray holds once everything has settled.

Examples

Example 1

Input
heightMap = [[9, 9, 9, 9, 9], [9, 2, 5, 1, 9], [9, 4, 0, 3, 9], [9, 9, 9, 9, 9]]
Output
39

Walls of 9 surround the tray, so the six inner cells fill to level 9, and the volume is what is left above each of their own heights.

Example 2

Input
heightMap = [[3, 3, 3], [3, 4, 3], [3, 3, 3]]
Output
0

The single inner cell stands taller than the wall around it, so nothing collects.

Example 3

Input
heightMap = [[5]]
Output
0

A tray one cell across has no inside at all, so nothing can be held.

Constraints

  • 1 <= heightMap.length <= 200
  • 1 <= heightMap[i].length <= 200
  • Every row of heightMap has the same length
  • 0 <= heightMap[i][j] <= 2 * 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def trap_rain_water(heightMap: list[list[int]]) -> int:
Java
public int trapRainWater(int[][] heightMap)

More on the same topics