LeetCode 407 · Queue · BFS

Trapping Rain Water II, explained with a picture

Rain on a block city, filled from the edges.

Queue · BFS
▶ Watch it step by step

The problem

Given a 2-D map of block heights, compute how much rain water is trapped on top.

Input:  1,4,3,1,3,2 / 3,2,1,3,2,4 / 2,3,3,2,3,1
Output: 4

Picture it

Picture rain on a city of blocks. Water can escape over the edges, so it can only rise to the lowest wall that surrounds it. Start with all border blocks in a min-heap and always process the lowest wall next. Any lower neighbour inside holds water up to that wall’s height.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Min-heap from the border inward (a Dijkstra-like flood). O(N log N).

Python solution

def trap_rain_water(h):
    heap, seen = [], set()
    for r, c in border_cells(h):
        heappush(heap, (h[r][c], r, c)); seen.add((r, c))
    water = 0
    while heap:
        level, r, c = heappop(heap)      # lowest wall first
        for nr, nc in neighbours(r, c):
            if (nr, nc) not in seen:
                seen.add((nr, nc))
                water += max(0, level - h[nr][nc])
                heappush(heap, (max(level, h[nr][nc]), nr, nc))
    return water

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.