Pattern visualizer

Pacific Atlantic Water Flow

Water moves to a neighbour of equal or lower height, so the honest question — 'can this cell drain to both oceans?' — asked once per cell re-walks the same downhill paths over and over. Turn it around: stand in an ocean and climb. A cell that can be reached by walking UPHILL from the Pacific border is exactly a cell whose water runs downhill back to the Pacific. One flood per ocean marks every cell that reaches it, and the answer is the cells both floods touched. Animated on: heights = [[6,1,7],[2,9,3],[8,4,5]]. The Pacific laps the top and left edges, the Atlantic the bottom and right. Find every cell whose water can reach both..

Two reverse BFS floods, one from each ocean

time O(rows * cols)space O(rows * cols)step 1 / 16

Heights — arrows point downhill, the way water runs

line 1

Water leaves a cell only for a neighbour at the same height or lower, so from (1,1) height 9 — the peak — it can run anywhere, while (0,1) height 1 can never feed anything. Asking "where can this cell drain to?" for all 9 cells repeats the same walks, so we invert it: start AT each ocean and climb, following those arrows backwards.

Pseudocode

1FUNCTION pacificAtlantic(H):
2  pac <- EMPTY SET
3  atl <- EMPTY SET
4  CLIMB(pac, PACIFIC BORDER)
5  CLIMB(atl, ATLANTIC BORDER)
6  RETURN pac INTERSECT atl
7FUNCTION CLIMB(seen, queue):
8  WHILE LENGTH(queue) > 0:
9    (r, c) <- REMOVE FIRST FROM queue
10    FOR (nr, nc) IN NEIGHBOURS(r, c):
11      IF (nr, nc) NOT IN seen AND H[nr][nc] >= H[r][c]:
12        ADD (nr, nc) TO seen
13        APPEND (nr, nc) TO queue

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap