HARD Lab · Graphs · 43

417. Pacific Atlantic Water Flow

Water flows from any cell to a neighbor of equal or lesser height, reaching the Pacific (top/left edges) or Atlantic (bottom/right edges). The trick: reverse the flow — DFS uphillfrom each ocean's border, then collect cells the two reachable sets share.

● MediumMulti-source DFS/BFSTypeScript

PROBLEM What we're solving

Given an R×C grid of heights, water at any cell can flow to an adjacent cell (up/down/left/right) of equal or lesser height. The Pacific Ocean borders the top and left edges; the Atlantic Ocean borders the bottom and right edges. Return all cells from which water can reach both oceans.

Example: for the 5×5 grid [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], the answer is [0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0].

KEY IDEA Reverse the flow — DFS uphill from each ocean border

Insight →Instead of asking “can water from cell X reach ocean Y?” (which requires an exhaustive search per cell), reverse the question: start at the ocean border and ask “which cells can feedthis ocean?” Water flows downhill, so reverse flow goes uphill — DFS to neighbors with height ≥ current. Do this once for each ocean, then intersect the two reachable sets.

RECIPE Two-pass multi-source DFS, then intersect

0 · Allocate two visited sets (pacific and atlantic) — one per ocean.
1 · Seed Pacific: enqueue every cell on the top row and left column. These cells border the Pacific and can trivially drain into it.
2 · DFS uphill from Pacific seeds: from each queued cell, explore 4-directional neighbors whose height is ≥ current height (reverse flow). Mark them in pacific.
3 · Seed Atlantic with bottom row + right column, then DFS uphill into atlantic.
4 · Intersect: collect every [r,c] present in both sets — these are the answer.

Classic confusion → The DFS condition is neighbor.height ≥ current.height (uphill, because flow is reversed), not neighbor.height ≤ current.height. Getting it backwards yields the wrong reachable set.

COST Complexity & alternatives

DFS from every cell

O(R²·C²)

Each of R·C cells starts its own full traversal.

Reverse multi-source DFS

O(R·C)

Each cell is visited at most once per ocean pass.

Space is also O(R·C) for the two visited sets and the implicit DFS call stack (worst case: the whole grid is reachable). You can replace the recursive DFS with an iterative BFS queue for the same complexity and no stack-overflow risk on large grids.

Pattern transfer →The “multi-source BFS/DFS from a known set of borders” pattern also solves Surrounded Regions(mark ‘O’ cells connected to the border so only isolated ones are flipped), Number of Enclaves (count land cells unreachable from border), and Walls and Gates (BFS from all zeros at once).

RUN IT DFS uphill from each ocean border, intersect the reachable sets

Heights (rows by ;, cols by ,)

step 0 / 35

STARTGrid loaded. We'll DFS from Pacific borders (top row + left col) uphill.

Pacific-reachableAtlantic-reachableBoth oceans (answer)Current cell

slowfast

TYPESCRIPT The solution, annotated

pacificAtlantic.ts
function pacificAtlantic(heights: number[][]): number[][] {
  const R = heights.length, C = heights[0].length;
  const pacific  = new Set<number>();
  const atlantic = new Set<number>();
  const idx = (r: number, c: number) => r * C + c;

  function dfs(r: number, c: number, reach: Set<number>): void {
    if (reach.has(idx(r, c))) return;
    reach.add(idx(r, c));
    const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
      if (reach.has(idx(nr, nc))) continue;
      if (heights[nr][nc] >= heights[r][c]) dfs(nr, nc, reach);
    }
  }

  // Seed Pacific: top row + left column
  for (let c = 0; c < C; c++) dfs(0, c, pacific);
  for (let r = 1; r < R; r++) dfs(r, 0, pacific);

  // Seed Atlantic: bottom row + right column
  for (let c = 0; c < C; c++) dfs(R - 1, c, atlantic);
  for (let r = 0; r < R - 1; r++) dfs(r, C - 1, atlantic);

  // Intersection
  const result: number[][] = [];
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (pacific.has(idx(r, c)) && atlantic.has(idx(r, c)))
        result.push([r, c]);
  return result;
}

Reading it block by block

Lines 2–5 — setup. We store reachability in two flat Set<number> objects keyed by r * C + c. The helper idx converts (row,col) → a unique integer, avoiding nested arrays.

Lines 7–14 — DFS uphill. The DFS takes a reach set as a parameter so the same function serves both oceans. It marks the current cell visited, then recurses into any in-bounds, not-yet-visited neighbor whose height is ≥ heights[r][c] — the reversal of normal downhill flow.

Lines 17–19 — seed Pacific. Every cell on the top row (r=0) and left column (c=0) is a border cell that trivially reaches the Pacific. We call dfs on each; the visited-check at line 8 prevents revisiting corners.

Lines 22–23 — seed Atlantic. Bottom row (r=R-1) and right column (c=C-1) seed the Atlantic pass identically.

Lines 26–30 — intersect. A nested loop over all cells; any cell present in both sets drains to both oceans. Collected into the result array.

Complexity → O(R·C) time — each cell enters each DFS at most once (the visited-set guard). O(R·C) space for the two sets plus the recursion stack (bounded by R·C in the worst case). An iterative BFS is a drop-in replacement that avoids stack growth.

INTERVIEWFollow-ups they'll ask

“Iterative BFS instead of recursive DFS?” Replace the dfs call with a queue seeded from the same border cells; enqueue each newly marked cell. Same O(R·C) complexity but avoids call-stack overflow on large grids.
“What if water must flow strictly downhill (no equal height)?” Change ≥ to > in the neighbor condition. The algorithm structure stays identical.
“What if there are multiple ‘oceans’?” Generalize to N reachable sets, one per ocean, and seed each from its border; intersect all sets at the end. The per-cell cost stays O(N) additional passes.
“Return the count instead of coordinates?” Trivial — return result.length. The real follow-up is whether you could count without materializing the result array (yes, just increment a counter).
“Edge case: 1×1 grid?” A single cell borders all four edges, so it reaches both oceans and is always in the answer.

MNEMONIC The one-liner

"Stand at the ocean shore and walk uphill — every cell you reach can drain back down to you."

TRIGGERS When you see _ → reach for _

water flow / reachability on a height grid	reverse DFS uphill from border
two sources, need cells reachable by both	two BFS/DFS sets + intersect
"cells connected to the border" (Surrounded Regions, Enclaves)	multi-source BFS from all border cells at once
naïve per-cell search is O(n²)	flip direction: seed from targets, single shared traversal

SKELETON The reusable shape

skeleton.ts
function pacificAtlantic(heights: number[][]): number[][] {
  const R = heights.length, C = heights[0].length;
  const pacific = new Set<number>(), atlantic = new Set<number>();
  const idx = (r: number, c: number) => r * C + c;

  function dfs(r: number, c: number, reach: Set<number>): void {
    if (reach.has(idx(r, c))) return;
    reach.add(idx(r, c));
    // explore 4-directional neighbors that are >= heights[r][c]
  }

  // seed pacific: top row + left col
  // seed atlantic: bottom row + right col
  // return intersection
}

FLASHCARDS Tap to flip

Why DFS uphill instead of downhill?

We reverse the flow direction: starting from the ocean border and moving to cells with height ≥ current is equivalent to asking which cells can drain down into the ocean.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 7

QUESTION 01

What is the time complexity of the reverse multi-source DFS solution?

QUESTION 02

In the reverse DFS, the condition to recurse into a neighbor is:

QUESTION 03

For a 1×1 grid with value 5, the answer is:

QUESTION 04

Which cells seed the Pacific DFS?

QUESTION 05

In the 5×5 example grid, cell [0,4] (height = 5, top-right corner) is in the answer because:

QUESTION 06

What space does the algorithm use?

QUESTION 07

Which pattern best describes this solution?

PROBLEM What we're solving

KEY IDEA Reverse the flow — DFS uphill from each ocean border

RECIPE Two-pass multi-source DFS, then intersect

COST Complexity & alternatives

RUN IT DFS uphill from each ocean border, intersect the reachable sets

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _