Data Structures & Algorithms · Graphs

Pacific Atlantic Water Flow: Flood the Oceans, Not the Cells

Q: Why does reversing the flow make Pacific Atlantic Water Flow faster?

A per-cell forward flood re-explores the same terrain from every starting cell with no memory between runs, which is O((m·n)²). Reversing the direction lets you flood from each ocean border exactly once, marking every cell reachable uphill. Two passes plus an intersection visit each cell a constant number of times, dropping the total to O(m·n).

Q: What is the time and space complexity of the DFS solution?

Both are O(m·n). Each of the two ocean passes marks a cell at most once thanks to its visited grid, so total visits are linear in the number of cells. Space is O(m·n) for the two boolean grids plus the DFS recursion stack, which in the worst case can go as deep as the cell count.

Q: Why does the height check use strict less-than?

The gate heights[r][c] < prevHeight returns early only when the next cell is strictly lower than where you came from. That leaves equal heights allowed, which matters because the problem says water flows to neighbors of equal-or-lower height. In the reverse flood, climbing to an equal-height cell is legal, so blocking it with <= would wrongly exclude flat regions.

Q: Do I need two separate visited grids, or can I use one?

You need two. The final answer is the set of cells reachable from both oceans, which you can only compute by keeping the Pacific and Atlantic reachability sets separate and intersecting them at the end. A single shared grid can't distinguish "reached from the Pacific" from "reached from the Atlantic," so the intersection information is lost.

Q: Can this be solved with BFS instead of DFS?

Yes. Seed a queue with all Pacific border cells and another with all Atlantic border cells, then run standard grid BFS with the same uphill (>=) expansion rule. BFS has identical O(m·n) time and space and avoids deep recursion, which is safer on very large grids where DFS could overflow the call stack. The intersection step at the end is unchanged.

Solve Pacific Atlantic Water Flow with reverse multi-source DFS from the ocean borders — intuition, JavaScript code, a worked walkthrough, and complexity.

July 17, 20267 min readBy Bhavesh Singh

graphsgrid dfsmulti-sourcegraph matrix dfsleetcode medium

This article has an interactive companion

Don't just read it — step through it interactively, one state change at a time.

Open the Pacific Atlantic Water Flow visualizer

Pacific Atlantic Water Flow looks like a physics simulation and gets solved like one — badly — by most people on the first try. They start a flood from every cell and watch it trickle downhill to the edges. That works, but it re-floods the same terrain thousands of times.

The trick that turns this from O((m·n)²) into O(m·n) is one word: reverse. Don't ask where water leaves the island. Ask where the ocean can climb to. Flood inward from each shoreline, uphill, and the answer is the overlap of the two floods.

The problem

You're given an m x n grid heights, where heights[r][c] is the elevation of one cell. The Pacific Ocean touches the top edge and the left edge; the Atlantic Ocean touches the bottom edge and the right edge. Water flows from a cell to any of its four neighbors whose height is equal or lower. A cell drains to an ocean if water can reach that ocean's border through a chain of such moves.

Return every coordinate [r, c] from which water can reach both oceans.

text

Input:  heights = [[1,2,1],
                   [2,5,2],
                   [1,2,1]]
Output: [[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1]]

Every cell except the two "trapped" corners — [0,0] and [2,2] — can send water to both shores. The central peak [1,1] = 5 is high enough to spill in any direction, so it drains everywhere.

The brute force baseline

The literal reading: for each cell, run a flood following the downhill rule and record which oceans it reaches.

javascript

function pacificAtlantic(heights) {
  const rows = heights.length, cols = heights[0].length;
  const res = [];

  function canDrain(r, c, seen) {
    // returns { pac, atl } — which borders this flow touches
    if (r < 0 || c < 0) return { pac: true, atl: false };   // Pacific edge
    if (r >= rows || c >= cols) return { pac: false, atl: true }; // Atlantic edge
    // ...recurse into every lower-or-equal neighbor, union the results
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      const { pac, atl } = canDrain(r, c, new Set());
      if (pac && atl) res.push([r, c]);
    }
  return res;
}

Each of the m·n cells launches its own flood that can touch up to m·n other cells, and nothing is cached between them. That's roughly O((m·n)²) work. On a modest 100×100 grid you're doing 100 million cell visits — and the code is fiddly, because a downhill flood can loop across equal-height plateaus if you don't track seen per launch.

The key insight: flood from the ocean, uphill

Flip the direction of the flow. If water can travel from cell X down to the Pacific border, then starting at that border you can travel up to X. Reachability is symmetric under a reversed comparison.

So run the flood only from the shorelines:

Seed a DFS from every Pacific border cell (top row + left column) and walk to any neighbor whose height is greater than or equal to the current one. Mark everything you touch as Pacific-reachable.
Do the same from every Atlantic border cell (bottom row + right column) into a second grid.
The answer is the intersection: cells marked in both grids.

This is the multi-source grid DFS pattern. Instead of m·n independent floods, you run exactly two flood passes, each visiting every cell at most once. The comparison flips from "downhill" (≤) to "uphill or flat" (≥), which is why the code checks heights[r][c] < prevHeight and bails when the next cell is too low to have drained here.

The optimal solution

This is the exact algorithm the visualizer animates — two border-seeded DFS passes into separate pacific and atlantic grids, then a final intersection sweep.

javascript

function pacificAtlantic(heights) {
  const rows = heights.length;
  const cols = heights[0].length;

  const pacific = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const atlantic = Array.from({ length: rows }, () => new Array(cols).fill(false));

  function dfs(r, c, visited, prevHeight) {
    if (r < 0 || r >= rows || c < 0 || c >= cols ||
        visited[r][c] || heights[r][c] < prevHeight) {
      return;
    }

    visited[r][c] = true;

    dfs(r + 1, c, visited, heights[r][c]);
    dfs(r - 1, c, visited, heights[r][c]);
    dfs(r, c + 1, visited, heights[r][c]);
    dfs(r, c - 1, visited, heights[r][c]);
  }

  // DFS inward from every border cell
  for (let c = 0; c < cols; c++) {
    dfs(0, c, pacific, heights[0][c]);
    dfs(rows - 1, c, atlantic, heights[rows - 1][c]);
  }
  for (let r = 0; r < rows; r++) {
    dfs(r, 0, pacific, heights[r][0]);
    dfs(r, cols - 1, atlantic, heights[r][cols - 1]);
  }

  const result = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (pacific[r][c] && atlantic[r][c]) {
        result.push([r, c]);
      }
    }
  }
  return result;
}

Two details carry the correctness. First, each border cell seeds the DFS with its own height as prevHeight, so the seed always passes the heights[r][c] < prevHeight gate and gets marked. Second, the gate uses strict <, which means an equal-height neighbor (heights[r][c] === prevHeight) is allowed through — flat water still flows, exactly as the problem specifies.

Walkthrough

Trace the Pacific DFS seeded at the top-left corner [0,0] on the peak grid. Columns show the call, the prevHeight passed in, the current cell's height, the gate result, and what happens. pac accumulates marked cells.

Call `dfs(r,c,prev)`	height	Gate check	Action	pacific marked
`dfs(0,0, 1)`	1	`1 < 1` false	mark `[0,0]`	{[0,0]}
↳ `dfs(1,0, 1)`	2	`2 < 1` false	mark `[1,0]`	+[1,0]
↳↳ `dfs(2,0, 2)`	1	`1 < 2` true	return (too low)	—
↳↳ `dfs(1,1, 2)`	5	`5 < 2` false	mark `[1,1]`	+[1,1]
↳↳↳ `dfs(2,1, 5)`	2	`2 < 5` true	return	—
↳↳↳ `dfs(0,1, 5)`	2	`2 < 5` true	return	—
↳↳↳ `dfs(1,2, 5)`	2	`2 < 5` true	return	—
↳ `dfs(0,1, 1)`	2	`2 < 1` false	mark `[0,1]`	+[0,1]
↳↳ `dfs(1,1, 2)`	5	visited	return	—
↳↳ `dfs(0,2, 2)`	1	`1 < 2` true	return	—

Notice the two ways a branch dies: it walks off the grid or downhill (heights[r][c] < prevHeight). The peak [1,1] = 5 gets marked because you climbed up to it from [1,0], but every branch out of the peak dies immediately — nothing around it is as tall. After all four Pacific seeds run, only the two low corners escape marking; the later Atlantic pass mirrors this from the opposite shores, and the intersection drops [0,0] and [2,2].

Complexity

Approach	Time	Space	Why
Per-cell downhill flood	O((m·n)²)	O(m·n)	every cell launches an uncached flood over the whole grid
Reverse multi-source DFS	O(m·n)	O(m·n)	each cell is visited at most twice — once per ocean pass

The two pacific / atlantic grids and the recursion stack each cost O(m·n), so space is linear in the grid size. Time is linear too: a cell already marked in a given visited grid is rejected instantly by the visited[r][c] gate, so no cell is expanded more than once per ocean.

Common mistakes

Flooding the wrong direction. The border DFS climbs uphill (heights[r][c] >= prevHeight). If you copy a "flow downhill" rule into the reverse pass, you mark the exact opposite set of cells.
Using <= instead of < in the gate. The bail condition is heights[r][c] < prevHeight. Writing <= blocks equal-height moves, and water is supposed to spread across flat plateaus.
Sharing one visited grid between both oceans. Pacific and Atlantic need separate grids; the whole answer is their intersection. One shared grid destroys the information you need at the end.
Forgetting the corners belong to both oceans. [0,0] sits on the Pacific border and [m-1,n-1] on the Atlantic border — the seed loops already cover them, but only if you seed every edge cell, including corners.
Returning cells marked in either set. The answer is the AND of the two grids (pacific[r][c] && atlantic[r][c]), not the OR.

Where this pattern shows up next

Border-seeded and multi-source graph traversal is a whole family of problems:

Redundant Connection — cycle detection on a graph, where union-find replaces the flood.
Course Schedule II — topological ordering, another "process from the frontier inward" traversal.
Shortest Path in Binary Matrix — grid BFS when you need distances, not just reachability.
Network Delay Time — single-source shortest paths on a weighted graph.

You can also step through Pacific Atlantic Water Flow interactively to watch the two floods spread from the shorelines and see the intersection light up cell by cell.

FAQ

Why does reversing the flow make Pacific Atlantic Water Flow faster?

A per-cell forward flood re-explores the same terrain from every starting cell with no memory between runs, which is O((m·n)²). Reversing the direction lets you flood from each ocean border exactly once, marking every cell reachable uphill. Two passes plus an intersection visit each cell a constant number of times, dropping the total to O(m·n).

What is the time and space complexity of the DFS solution?

Both are O(m·n). Each of the two ocean passes marks a cell at most once thanks to its visited grid, so total visits are linear in the number of cells. Space is O(m·n) for the two boolean grids plus the DFS recursion stack, which in the worst case can go as deep as the cell count.

Why does the height check use strict less-than?

The gate heights[r][c] < prevHeight returns early only when the next cell is strictly lower than where you came from. That leaves equal heights allowed, which matters because the problem says water flows to neighbors of equal-or-lower height. In the reverse flood, climbing to an equal-height cell is legal, so blocking it with <= would wrongly exclude flat regions.

Do I need two separate visited grids, or can I use one?

You need two. The final answer is the set of cells reachable from both oceans, which you can only compute by keeping the Pacific and Atlantic reachability sets separate and intersecting them at the end. A single shared grid can't distinguish "reached from the Pacific" from "reached from the Atlantic," so the intersection information is lost.

Can this be solved with BFS instead of DFS?

Yes. Seed a queue with all Pacific border cells and another with all Atlantic border cells, then run standard grid BFS with the same uphill (>=) expansion rule. BFS has identical O(m·n) time and space and avoids deep recursion, which is safer on very large grids where DFS could overflow the call stack. The intersection step at the end is unchanged.

Make it stick: run this one yourself

Don't just read it — step through it interactively, one state change at a time.

Open the Pacific Atlantic Water Flow visualizer

The problem#

The brute force baseline#

The key insight: flood from the ocean, uphill#

The optimal solution#

Walkthrough#

Complexity#

Common mistakes#

Where this pattern shows up next#

FAQ#

Why does reversing the flow make Pacific Atlantic Water Flow faster?#

What is the time and space complexity of the DFS solution?#

Why does the height check use strict less-than?#

Do I need two separate visited grids, or can I use one?#

Can this be solved with BFS instead of DFS?#

Related articles