Typorithm · medium

Pacific Atlantic Water Flow

pacific-atlanticgraphsreverse-flowborder-dfsintersection

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Pacific Atlantic Water Flow

Graphs

Reverse the flow: DFS inward from each ocean's border climbing uphill, then return cells reachable from BOTH oceans.

Simulating downhill flow from every cell is expensive; instead, reverse it and flow up from the oceans.

From each ocean's border, DFS to any neighbor at least as high, marking reachable cells.

A cell drains to both oceans exactly when both reachability grids mark it.

Reverse the flow from the borders.

Climb to equal-or-higher cells.

Answer = reachable by both oceans.

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, seen, prev) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || seen[r][c] || heights[r][c] < prev) {
      return;
    }
    seen[r][c] = true;
    dfs(r + 1, c, seen, heights[r][c]);
    dfs(r - 1, c, seen, heights[r][c]);
    dfs(r, c + 1, seen, heights[r][c]);
    dfs(r, c - 1, seen, heights[r][c]);
  }

  for (let r = 0; r < rows; r += 1) {
    dfs(r, 0, pacific, -Infinity);
    dfs(r, cols - 1, atlantic, -Infinity);
  }
  for (let c = 0; c < cols; c += 1) {
    dfs(0, c, pacific, -Infinity);
    dfs(rows - 1, c, atlantic, -Infinity);
  }

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

  return result;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Reachability grid

Track which cells can reach each ocean.

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

2. Climb uphill

Reversing flow, move only to cells at least as high.

heights[r][c] < prev

3. Start at oceans

Seed DFS from the border cells touching each ocean.

dfs(r, 0, pacific, -Infinity);
    dfs(r, cols - 1, atlantic, -Infinity)

4. Reaches both

Answer cells flow to the Pacific AND the Atlantic.

if (pacific[r][c] && atlantic[r][c]) {

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.