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 waterLeetCode 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.