Pacific Atlantic Water Flow

Examples

Input: heights = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[0,2],[1,2],[2,0],[2,1],[2,2]]

Heights strictly increase toward the bottom-right, so every cell can always step up-or-left to lower ground and reach the Pacific. But the only cells that can reach the Atlantic are the ones already sitting on its border, since moving toward the bottom/right edges only ever goes uphill.

Input: heights = [[3,3],[3,3]]
Output: [[0,0],[0,1],[1,0],[1,1]]

The whole grid is flat, and flowing across equal height is allowed, so every cell can reach both oceans.

Constraints

• 1 <= rows, cols <= 200

• 0 <= heights[i][j] <= 10^5

Approach

Trying every cell's path out to both oceans one at a time works, but it redoes a lot of the same traversal over and over. There's a much cheaper way to get the same answer: run the traversal in reverse, starting from the oceans themselves.

Water flows from a higher (or equal) cell to a lower (or equal) neighbor. So instead of asking "starting at this cell, can I reach the Pacific?", flip the question around: "starting at the Pacific's border cells, which cells could have flowed into them?" A cell can flow into its neighbor if the neighbor's height is less than or equal to its own - so walking in reverse, you move from a cell to a neighbor whenever that neighbor's height is greater than or equal to the current one.

Do this reverse flood-fill twice: once starting from every cell on the Pacific's two border edges, marking everything reachable as "reaches Pacific," and once starting from every cell on the Atlantic's two border edges, marking everything reachable as "reaches Atlantic." A cell that ends up marked by both searches is exactly a cell that can flow to both oceans.

Solutions

Brute Force - Trace a Path From Every Cell

For each cell, run a DFS that only steps to equal-or-lower neighbors, and see whether that DFS ever reaches a Pacific-border cell; separately check the same way for the Atlantic. A cell only makes it into the result if both checks succeed.

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

  function canReach(startR, startC, isBorder) {
    const seen = new Set();

    function dfs(r, c) {
      const key = r + "," + c;
      if (seen.has(key)) return false;
      seen.add(key);

      if (isBorder(r, c)) return true;

      const neighbors = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]];
      for (const [nr, nc] of neighbors) {
        if (
          nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
          heights[nr][nc] <= heights[r][c] &&
          dfs(nr, nc)
        ) {
          return true;
        }
      }

      return false;
    }

    return dfs(startR, startC);
  }

  const touchesPacific = (r, c) => r === 0 || c === 0;
  const touchesAtlantic = (r, c) => r === rows - 1 || c === cols - 1;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (canReach(r, c, touchesPacific) && canReach(r, c, touchesAtlantic)) {
        result.push([r, c]);
      }
    }
  }

  return result;
}

Time: O((rows × cols)²) · Space: O(rows × cols)

Optimal - Reverse Multi-Source Flood Fill

Run a flood fill from every Pacific-border cell at once, stepping to a neighbor whenever its height is greater than or equal to the current cell's - this marks every cell that can flow to the Pacific. Do the same from every Atlantic-border cell. A cell marked reachable in both flood fills belongs in the answer.

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) {
    visited[r][c] = true;

    const neighbors = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]];
    for (const [nr, nc] of neighbors) {
      if (
        nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
        !visited[nr][nc] &&
        heights[nr][nc] >= heights[r][c]
      ) {
        dfs(nr, nc, visited);
      }
    }
  }

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

  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;
}

Time: O(rows × cols) · Space: O(rows × cols)