Pacific Atlantic Water Flow

1. Define the problem

You are given an m x n matrix of heights representing a continent. The Pacific Ocean touches the top and left edges; the Atlantic touches the bottom and right edges. Water can flow from a cell to a 4-directional neighbor with a height that is less than or equal to it. Return every cell from which water can reach both oceans. Rather than searching forward from every cell, search backward from each ocean's border , using depth-first search that only steps to a neighbor whose height is greater than or equal to the current cell — that traces every path water could have taken to reach the border.

Constraints

m == heights.length
n == heights_i.length
1 ≤ m, n ≤ 200
0 ≤ heights_i[j] ≤ 10⁵

Example

Inputheights = [[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]]

Explanation These are exactly the cells from which a non-increasing path exists to both the top/left border and the bottom/right border.

2. Know the words first

In plain terms

Border cell: A cell already touching an ocean — every cell in the top or left row/column touches the Pacific, and every cell in the bottom or right row/column touches the Atlantic.

3. Visualize the solution

Search uphill from each ocean border, then intersect

Statuspacific from the top row

Every border cell of height 5 reverse-flows into equal-or-taller neighbors.

What happens in this step

pacific dfs seeds: index 0, 1, 2 (top row, height 5 each) and index 0, 3, 6 (left column)

From index 0 (height 5): neighbor index 3 (down, height 5) → 5 >= 5, step in
                          neighbor index 1 (right, height 5) → 5 >= 5, step in

Water can flow backward onto a border cell only from a neighbor at least as tall, so the search steps outward along the ring of 5s and hasn't touched the center yet.

Step 1 of 4

Steps to visualize

Run a depth-first search from every top-row and left-column cell, stepping to a neighbor only if it is taller or equal — this marks everywhere that can drain to the Pacific.
Run the same search from every bottom-row and right-column cell to mark everywhere that can drain to the Atlantic.
A cell surrounded only by taller neighbors, and not itself on a border, is unreachable from that ocean — water pools there instead.
The answer is every cell marked reachable by both searches.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Search uphill from each ocean border, then intersect

Statuspacific from the top row

Every border cell of height 5 reverse-flows into equal-or-taller neighbors.

What happens in this step

pacific dfs seeds: index 0, 1, 2 (top row, height 5 each) and index 0, 3, 6 (left column)

From index 0 (height 5): neighbor index 3 (down, height 5) → 5 >= 5, step in
                          neighbor index 1 (right, height 5) → 5 >= 5, step in

Water can flow backward onto a border cell only from a neighbor at least as tall, so the search steps outward along the ring of 5s and hasn't touched the center yet.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function pacificAtlantic(heights) {
  const rows = heights.length;
  const cols = heights[0].length;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  function dfs(r, c, visited) {
    visited[r][c] = true;

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (visited[nr][nc]) continue;
      if (heights[nr][nc] < heights[r][c]) continue;

      dfs(nr, nc, visited);
    }
  }

  const pacific = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const atlantic = Array.from({ length: rows }, () => new Array(cols).fill(false));

  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)

6. Test cases

Test cases

Input	Expected	Covers
`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]]`	`[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]`	example from the docstring
`heights = [[1,1],[1,1]]`	`[[0,0],[0,1],[1,0],[1,1]]`	a flat grid lets water flow to both oceans everywhere
`heights = [[5]]`	`[[0,0]]`	a single cell touches every border at once
`heights = [[1,2,3]]`	`[[0,0],[0,1],[0,2]]`	a single row is simultaneously the top and bottom border
`heights = [[1],[2],[3]]`	`[[0,0],[1,0],[2,0]]`	a single column is simultaneously the left and right border
`heights = [[5,5,5],[5,1,5],[5,5,5]]`	`[[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]`	a low interior cell surrounded by higher walls cannot drain to either ocean
`heights = [[1,2,3],[4,5,6],[7,8,9]]`	`[[0,2],[1,2],[2,0],[2,1],[2,2]]`	a strictly increasing grid where only the Atlantic side is hard to reach

Pacific Atlantic Water Flow