407. Trapping Rain Water II

Push every border cell into a min-heap and mark visited. Loop: pop the shortest border (h, r, c). For each unvisited 4-neighbor (nr, nc) with height nh: if nh < h, water += h - nh (this cell sits below the weakest wall surrounding it). Push (max(h, nh), nr, nc) — the effective wall for cells beyond this one is the *higher* of h and nh, because water now has to surmount the current frontier. Mark visited. Continue until the heap empties. This is BFS/Dijkstra in spirit: you're always processing the lowest known wall, which guarantees that when you visit an interior cell, all paths to the boundary go through walls at least as high. O(mn log(mn)) time. Why not 1D's two-pointer? In 2D, 'left wall' and 'right wall' aren't well-defined — water can escape in any direction.