Pacific Atlantic Water Flow

The problem

heights[r][c] is elevation. Water flows to 4-neighbors with height ≤ current (non-increasing path). Pacific touches top and left borders; Atlantic bottom and right. Return all coordinates that can flow to both oceans.

Input heights:
[[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]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Flip the intuition: instead of flowing down from each cell (expensive), flood uphill from ocean borders (can reach if neighbor ≥ current).

Brute force

From every cell DFS if path reaches Pacific and separately Atlantic. O((mn)²) worst.

Optimal: two multi-source floods

1. DFS/BFS from all Pacific-border cells, mark reachable.
2. Same for Atlantic.
3. Intersection of the two reachable sets.

function pacificAtlantic(heights: number[][]): number[][] {
  const rows = heights.length;
  if (!rows) return [];
  const cols = heights[0].length;
  const pac = Array.from({ length: rows }, () => Array(cols).fill(false));
  const atl = Array.from({ length: rows }, () => Array(cols).fill(false));
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  function dfs(r: number, c: number, seen: boolean[][]): void {
    seen[r][c] = true;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (seen[nr][nc]) continue;
      if (heights[nr][nc] < heights[r][c]) continue; // must go uphill or flat reverse
      dfs(nr, nc, seen);
    }
  }

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

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

Time	O(m · n)
Space	O(m · n)

Edge cases

• 1×1 grid → that cell reaches both
• Strictly decreasing toward one ocean only
• Flat plateaus — equal height is allowed
• Long thin grids

Common bugs

• Flowing downhill from borders (wrong direction for reverse flood)
• 8-connectivity
• Not marking visited → stack overflow
• Comparing > instead of >= for reverse flow

Interview delivery

1. Reframe as reverse multi-source.
2. Two visited matrices.
3. Intersection.
4. O(mn).
5. Mention BFS queue version for stack safety.

Related

• Number of Islands
• Max Area of Island
• Word Search
• Clone Graph

Reverse flow intuition

Water flows down to oceans. A cell can reach an ocean iff there’s a non-increasing path to that ocean. Equivalently, from the ocean, you can climb to cells along non-decreasing paths. Multi-source DFS from shores marks all cells that can drain there.

Why not one DFS per cell

O(mn) cells × O(mn) exploration = too slow. Two floods total O(mn).

BFS version

Push all Pacific border cells into a queue with a visited matrix; same for Atlantic. Prefer BFS if recursion depth on large grids worries you.

Further reading

• LeetCode 417 — Pacific Atlantic Water Flow
• Flood fill