Q47: Pacific Atlantic Water Flow (Graph Multi-Source DFS)

Find grid coordinate cells where rain water can flow to both Pacific (top/left) and Atlantic (bottom/right) oceans.

Reverse Flow Boundary DFS

function pacificAtlantic(heights) {
  if (!heights || !heights.length) return [];
  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, reachable, prevHeight) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || reachable[r][c] || heights[r][c] < prevHeight) {
      return;
    }
    reachable[r][c] = true;
    dfs(r + 1, c, reachable, heights[r][c]);
    dfs(r - 1, c, reachable, heights[r][c]);
    dfs(r, c + 1, reachable, heights[r][c]);
    dfs(r, c - 1, reachable, heights[r][c]);
  }
  
  for (let r = 0; r < rows; r++) {
    dfs(r, 0, pacific, heights[r][0]);                // Left Pacific
    dfs(r, cols - 1, atlantic, heights[r][cols - 1]); // Right Atlantic
  }
  for (let c = 0; c < cols; c++) {
    dfs(0, c, pacific, heights[0][c]);                // Top Pacific
    dfs(rows - 1, c, atlantic, heights[rows - 1][c]); // Bottom 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;
}

💡 Runs DFS backward from Pacific edges and Atlantic edges upstream (heights[r][c] >= prevHeight). Cells marked true in both boolean grids are returned.

Key Takeaways

Reverse flow simulation: DFS outward from ocean boundaries upstream to reachable higher/equal elevation land cells.
Cells reachable by both Pacific DFS and Atlantic DFS are valid answer coordinates.

Knowledge Check

Why does the algorithm perform DFS backward from ocean boundaries instead of forward from every cell?

Q47: Pacific Atlantic Water Flow (Graph Multi-Source DFS)

STAY UPDATED WITH BYTES!