0946HardArrayBreadth-First SearchHeap (Priority Queue)Matrix

Water Held by a Moulded Tray

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def trap_rain_water(heightMap: list[list[int]]) -> int:

Java

public int trapRainWater(int[][] heightMap)

The intended approach

Time O(m * n log(m * n)) for an m by n tray: every cell enters the heap once.Space O(m * n) for the heap and the settled marks.

The water level over a cell is decided by the lowest wall along the easiest route from that cell to the outside: whatever route needs the least height to climb over sets the level, and that level is the largest wall on that route. Work inwards from the edge, always settling the cell with the lowest known level next, which is what a heap keyed on level gives. Every edge cell starts at its own height, since water there runs straight off. Taking the lowest unsettled cell and looking at its neighbours, a neighbour's level is the larger of its own height and the level just settled, because water reaching it has to get over that boundary to leave. Settling in increasing order of level means a cell is never settled before the route that decides it, so each cell is settled once. The volume is then the level less the height, added over the cells.

Pythonentry point: trap_rain_water

def trap_rain_water(heightMap):
    import heapq
    m = len(heightMap)
    n = len(heightMap[0])
    if m < 3 or n < 3:
        return 0
    settled = [[False] * n for _ in range(m)]
    heap = []
    for r in range(m):
        for c in range(n):
            if r == 0 or c == 0 or r == m - 1 or c == n - 1:
                settled[r][c] = True
                heapq.heappush(heap, (heightMap[r][c], r, c))
    total = 0
    while heap:
        level, r, c = heapq.heappop(heap)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r + dr
            nc = c + dc
            if nr < 0 or nc < 0 or nr >= m or nc >= n:
                continue
            if settled[nr][nc]:
                continue
            settled[nr][nc] = True
            here = heightMap[nr][nc]
            if here < level:
                total += level - here
                heapq.heappush(heap, (level, nr, nc))
            else:
                heapq.heappush(heap, (here, nr, nc))
    return total

The obvious version

Start every inner cell at the highest level in the tray and every edge cell at its own height, then sweep the tray over and over, lowering each inner cell to the larger of its own height and the lowest level among its neighbours, until nothing changes. Settles by repeated relaxation rather than by any ordering, and pays for many sweeps.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_trap_rain_water(heightMap):
    m = len(heightMap)
    n = len(heightMap[0])
    if m < 3 or n < 3:
        return 0
    tallest = 0
    for row in heightMap:
        for v in row:
            if v > tallest:
                tallest = v
    level = [[tallest] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            if r == 0 or c == 0 or r == m - 1 or c == n - 1:
                level[r][c] = heightMap[r][c]
    changed = True
    while changed:
        changed = False
        for r in range(1, m - 1):
            for c in range(1, n - 1):
                lowest = None
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr = r + dr
                    nc = c + dc
                    if lowest is None or level[nr][nc] < lowest:
                        lowest = level[nr][nc]
                want = heightMap[r][c]
                if lowest > want:
                    want = lowest
                if want < level[r][c]:
                    level[r][c] = want
                    changed = True
    total = 0
    for r in range(m):
        for c in range(n):
            total += level[r][c] - heightMap[r][c]
    return total

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in