loading

Pacific Atlantic Water Flow — Step-by-Step Visualization

mediumLeetCode #417ArrayDepth-First SearchBreadth-First SearchMatrix

There is an `m x n` rectangular island that borders both the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). Water can flow from a cell to adjacent cells with equal or lower height. Return a list of cells from which water can flow to both the Pacific and Atlantic oceans.

Algorithm Pattern

Multi-source BFS (Reverse Flow)

Key Idea

Instead of flowing water downhill from each cell, do BFS uphill from each ocean's border. A cell reachable from both BFS traversals can flow to both oceans.

Step-by-Step Approach

  1. Initialize Pacific BFS queue with top row + left column.
  2. Initialize Atlantic BFS queue with bottom row + right column.
  3. BFS uphill (only move to neighbors with height >= current).
  4. Cells in both visited sets are the answer.

Common Gotchas

  • Water flows to equal or lower height — BFS goes to equal or higher height (reverse).
  • Two separate BFS runs, not one combined pass.

Related Problems

← All problems