Pacific Atlantic Water Flow

MediumGraphsArrayDFSBFSMatrix

Problem

You are given a grid of heights representing terrain, where the Pacific Ocean touches the top and left edges and the Atlantic Ocean touches the bottom and right edges. Water can flow from a cell to an orthogonal neighbor only if the neighbor's height is less than or equal to the current cell's height. Return every cell from which water can eventually reach both oceans.

Example. A corner cell bordering both the top edge and the left edge always reaches the Pacific directly, and if its height is high enough to flow down and right toward the bottom-right corner, it can reach the Atlantic too.

Key idea

Testing every cell by simulating its outward flow to see whether it reaches both oceans is expensive, since each simulation can itself touch much of the grid. The efficient move is to reverse the question: instead of asking which cells can flow out to the ocean, ask which cells the ocean could reach by flowing backward, uphill, from the coastline inward. Run a flood fill (depth-first or breadth-first) starting from every cell along the Pacific-adjacent edges, moving to a neighbor only when its height is greater than or equal to the current cell's (the reverse of the original rule) and mark every cell reached as Pacific-reachable. Repeat the same reverse flood fill from the Atlantic-adjacent edges. A cell marked by both flood fills is exactly one that true, forward-direction water could drain from to reach both oceans.

Solution

function pacificAtlantic(heights: number[][]): number[][] {
  const rows = heights.length;
  const cols = heights[0].length;
  const pacific = Array.from({ length: rows }, () => new Array<boolean>(cols).fill(false));
  const atlantic = Array.from({ length: rows }, () => new Array<boolean>(cols).fill(false));

  function flood(row: number, col: number, reachable: boolean[][]): void {
    reachable[row][col] = true; // mark reachable by reverse flow from this ocean
    const directions = [
      [1, 0],
      [-1, 0],
      [0, 1],
      [0, -1],
    ];
    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;
      if (
        newRow >= 0 &&
        newRow < rows &&
        newCol >= 0 &&
        newCol < cols &&
        !reachable[newRow][newCol] &&
        heights[newRow][newCol] >= heights[row][col] // reversed: uphill or equal, flowing backward
      ) {
        flood(newRow, newCol, reachable);
      }
    }
  }

  for (let row = 0; row < rows; row++) {
    flood(row, 0, pacific);
    flood(row, cols - 1, atlantic);
  }
  for (let col = 0; col < cols; col++) {
    flood(0, col, pacific);
    flood(rows - 1, col, atlantic);
  }

  const result: number[][] = [];
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (pacific[row][col] && atlantic[row][col]) { // reachable from both oceans' reverse flood fills
        result.push([row, col]);
      }
    }
  }

  return result;
}

Complexity

  • Time: O(rows × cols). Two flood fills, each visiting every cell at most once.
  • Space: O(rows × cols). Two reachability grids plus recursion or queue overhead.

Watch out for

  • The comparison direction flips: reverse flow moves to equal-or-taller neighbors, not equal-or-shorter ones.
  • Corner cells bordering two edges of the same ocean are still just one starting point for that ocean's flood fill.
  • Skip a cell already marked reachable for a given ocean instead of flooding from it again.

Pattern

This is boundary-seeded flood fill combined with intersecting two reachability sets, a reverse-of-the-obvious-direction trick that also solves Surrounded Regions.

Related questions