Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgraph-dfs

Pacific Atlantic Water Flow

Problem (restated)

An m × n height map. Water at a cell can flow 4-directionally to a neighbor of equal or lower height. The Pacific touches the top and left borders; the Atlantic the bottom and right. Return every cell from which water can reach both oceans.

Intuition

Forward search from every cell is O((mn)²). Reverse it: water that can flow to an ocean is the same as “ocean can climb to equal-or-higher cells.” DFS inland from each ocean’s border, then take the intersection of the two reachable sets.

Approaches

Two DFS from oceans

Unverified

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

Idea. pac and atl boolean grids. From Pacific borders (row 0, col 0) and Atlantic borders (row m-1, col n-1), DFS to a neighbor if heights[next] >= heights[cur] and not yet seen. Cells marked in both grids are the answer.

Walkthrough. Peak cells and ocean-border cells usually appear. A low interior pit that cannot climb to both coasts does not.

Trade-offs. Each cell is visited at most twice (once per ocean), so linear. Starting from the oceans is the trick; starting from every cell TLE’s. Corner cells sit on both oceans and are always included.

Solution

export function pacificAtlantic(heights: number[][]): number[][] {
  if (!heights.length) return [];
  const m = heights.length, n = heights[0]!.length;
  const pac = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const atl = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const dfs = (r: number, c: number, seen: boolean[][]) => {
    seen[r]![c] = true;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (seen[nr]![nc] || heights[nr]![nc]! < heights[r]![c]!) continue;
      dfs(nr, nc, seen);
    }
  };
  for (let c = 0; c < n; c++) { dfs(0, c, pac); dfs(m - 1, c, atl); }
  for (let r = 0; r < m; r++) { dfs(r, 0, pac); dfs(r, n - 1, atl); }
  const out: number[][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (pac[r]![c] && atl[r]![c]) out.push([r, c]);
  return out;
}

export function pacificAtlantic(heights: number[][]): number[][] {
  if (!heights.length) return [];
  const m = heights.length, n = heights[0]!.length;
  const pac = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const atl = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const dfs = (r: number, c: number, seen: boolean[][]) => {
    seen[r]![c] = true;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (seen[nr]![nc] || heights[nr]![nc]! < heights[r]![c]!) continue;
      dfs(nr, nc, seen);
    }
  };
  for (let c = 0; c < n; c++) { dfs(0, c, pac); dfs(m - 1, c, atl); }
  for (let r = 0; r < m; r++) { dfs(r, 0, pac); dfs(r, n - 1, atl); }
  const out: number[][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (pac[r]![c] && atl[r]![c]) out.push([r, c]);
  return out;
}

Template connection

Pacific-Atlantic shape of Graph DFS: two reverse flood fills from the borders, then intersect. Same 4-neighbor DFS as LC 733, with a height gate instead of a color match.

Reflection

DFS inward from each ocean’s shore, climbing when the neighbor is >= the current cell. Cells reached from both oceans are the answer.
This walk goes uphill from the shore. Looking only downhill never marks an interior cell.
One cell touches both oceans. A flat plateau is entirely reachable. A corner belongs to both shores.