DSA Tracker

Visualize

Pacific Atlantic Water Flow

Two reverse BFS floods, one from each ocean

time O(rows * cols)space O(rows * cols)

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.

Details

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.

Problem:Pacific Atlantic Water FlowMedium

Two reverse BFS floods, one from each ocean

step 1 / 16

Heights — arrows point downhill, the way water runs

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

Every step in words

Show all 16 steps
  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.
  2. Every cell touching the Pacific drains into it for free, so all 5 border cells start in the set. The queue holds them in row-major order; each one we pop asks which neighbours could have fed IT.
  3. Pop (0,0) height 6. Its unclaimed neighbours ((1,0) height 2, (0,1) height 1) all sit lower, so nothing new drains through here — water only ever leaves them. 4 cells still queued.
  4. Pop (0,1) height 1. (1,1) height 9 sits higher, so water there flows down into (0,1) height 1 and onward to the Pacific — add it to the set. 4 cells still queued.
  5. Pop (0,2) height 7. Its unclaimed neighbours ((1,2) height 3, (0,1) height 1) all sit lower, so nothing new drains through here — water only ever leaves them. 3 cells still queued.
  6. Pop (1,0) height 2. Its unclaimed neighbours (none) all sit lower, so nothing new drains through here — water only ever leaves them. 2 cells still queued.
  7. Pop (2,0) height 8. Its unclaimed neighbours ((1,0) height 2, (2,1) height 4) all sit lower, so nothing new drains through here — water only ever leaves them. 1 cell still queued.
  8. Pop (1,1) height 9. Its unclaimed neighbours ((0,1) height 1, (2,1) height 4, (1,0) height 2, (1,2) height 3) all sit lower, so nothing new drains through here — water only ever leaves them. Queue empty — the Pacific set is final at 6 cells.
  9. Every cell touching the Atlantic drains into it for free, so all 5 border cells start in the set. The queue holds them in row-major order; each one we pop asks which neighbours could have fed IT.
  10. Pop (0,2) height 7. Its unclaimed neighbours ((1,2) height 3, (0,1) height 1) all sit lower, so nothing new drains through here — water only ever leaves them. 4 cells still queued.
  11. Pop (1,2) height 3. (1,1) height 9 sits higher, so water there flows down into (1,2) height 3 and onward to the Atlantic — add it to the set. 4 cells still queued.
  12. Pop (2,0) height 8. Its unclaimed neighbours ((1,0) height 2, (2,1) height 4) all sit lower, so nothing new drains through here — water only ever leaves them. 3 cells still queued.
  13. Pop (2,1) height 4. Its unclaimed neighbours (none) all sit lower, so nothing new drains through here — water only ever leaves them. 2 cells still queued.
  14. Pop (2,2) height 5. Its unclaimed neighbours ((1,2) height 3, (2,1) height 4) all sit lower, so nothing new drains through here — water only ever leaves them. 1 cell still queued.
  15. Pop (1,1) height 9. Its unclaimed neighbours ((0,1) height 1, (2,1) height 4, (1,0) height 2, (1,2) height 3) all sit lower, so nothing new drains through here — water only ever leaves them. Queue empty — the Atlantic set is final at 6 cells.
  16. 3 cells carry both badges — (0,2) height 7, (1,1) height 9, (2,0) height 8. Two climbs over 9 cells answered it once; simulating a drain from every cell separately would have re-walked the same downhill paths 9 times.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Pacific Atlantic Water Flow in the editorAll Graph problemsBack to roadmap