Pacific Atlantic Water Flow

Reverse BFS from Ocean Edges

LeetCode 417 • Medium • Graphs

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] → Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Find cells where water can flow to both Pacific (top+left) and Atlantic (bottom+right). Reverse BFS from ocean edges inward.

TimeO(m·n)two BFS passes

SpaceO(m·n)sets + queue

Pacific: 0 Atlantic: 0 Both: 0 Step: 0/11

Pacific

Atlantic

Both Oceans

BFS Frontier

Ready

Press Play to watch reverse BFS discover cells reachable from each ocean, or Step to advance one wave at a time.

Speed:

✎ Whiteboard

Size: 3

⌨ Type It — Build Muscle Memory

Practice until you don't need to look. Use the guide comments below as scaffolding. Type the full implementation in the editor. The green highlights are the nuances to burn into memory.

═══ PACIFIC ATLANTIC — REVERSE BFS ═══

PATTERN ▸ BFS from ocean edges, find intersection O(m·n) · O(m·n)

① INIT sets for Pacific and Atlantic reachable cells

pacific = set(); atlantic = set()

② BFS from Pacific borders (top row + left col)

queue = deque(starts); expand to neighbors with height >= current

reachable.add((nr, nc)); queue.append((nr, nc))

③ BFS from Atlantic borders (bottom row + right col)

same BFS, separate set

④ INTERSECTION

return cells in BOTH pacific AND atlantic sets

sorted([list(c) for c in pacific & atlantic])

▼ your implementation ▼

Verify your solution: