Pacific Atlantic Water Flow

An island is described by an m x n grid heights, where heights[r][c] is the elevation of the cell in row r and column c. The Pacific Ocean touches the island along its top and left edges, and the Atlantic Ocean touches it along the bottom and right edges.

Rain falling on a cell can flow to any of the four orthogonally adjacent cells whose elevation is less than or equal to the current one. A cell on the border can also pour directly into every ocean that border touches (a corner cell may touch both).

Return the coordinates [r, c] of every cell from which rainwater can reach both oceans. The cells may be returned in any order.

Example 1

Example 2

Example 3

Constraints

• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

Pattern Path · Graphs: Traversal · problem 133 of 169

Start simple

Run a separate BFS/DFS downhill from every cell and check whether it touches both oceans: O((m·n)²) time.

The key idea

Water flows downhill, so a cell can drain into an ocean exactly when there is a path from the ocean's shore up to that cell where the elevation never decreases. Reversing the direction of the flow turns one search per cell into one search per ocean.

Seed a queue with every cell that borders the Pacific (top row and left column) and expand to neighbours whose height is >= the current cell. Every cell visited can send water to the Pacific. Repeat from the Atlantic shore (bottom row and right column). The answer is the set of cells visited by both searches.

Each search visits every cell at most once and looks at four neighbours, so the whole thing is linear in the grid size. Using BFS (or an explicit stack) instead of recursion keeps it safe on a 200 x 200 grid where a recursive DFS could go 40,000 calls deep.

Complexity

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

Python

from collections import deque


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        rows, cols = len(heights), len(heights[0])

        def reachable(starts):
            # Walk *uphill* from the ocean's shore: every cell we reach can drain into that ocean.
            seen = set(starts)
            queue = deque(starts)
            while queue:
                r, c = queue.popleft()
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if (0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen
                            and heights[nr][nc] >= heights[r][c]):
                        seen.add((nr, nc))
                        queue.append((nr, nc))
            return seen

        pacific = [(0, c) for c in range(cols)] + [(r, 0) for r in range(1, rows)]
        atlantic = [(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows - 1)]
        both = reachable(pacific) & reachable(atlantic)
        return [[r, c] for r, c in sorted(both)]

JavaScript

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

  // Walk uphill from the ocean's shore; every cell reached can drain into that ocean.
  const reachable = (starts) => {
    const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
    const queue = [];
    for (const [r, c] of starts) {
      if (!seen[r][c]) { seen[r][c] = true; queue.push([r, c]); }
    }
    for (let head = 0; head < queue.length; head++) {
      const [r, c] = queue[head];
      for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !seen[nr][nc]
            && heights[nr][nc] >= heights[r][c]) {
          seen[nr][nc] = true;
          queue.push([nr, nc]);
        }
      }
    }
    return seen;
  };

  const pacificStarts = [], atlanticStarts = [];
  for (let c = 0; c < cols; c++) { pacificStarts.push([0, c]); atlanticStarts.push([rows - 1, c]); }
  for (let r = 0; r < rows; r++) { pacificStarts.push([r, 0]); atlanticStarts.push([r, cols - 1]); }

  const pacific = reachable(pacificStarts), atlantic = reachable(atlanticStarts);
  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;
};

What the interviewer is checking

The interviewer wants to see you reverse the direction of a search and use multi-source BFS/DFS, rather than launching a costly search from every cell.

Mistakes to avoid

• Using a strict "greater than" when climbing: water flows across equal heights, so plateaus must be included.
• Forgetting that corner cells belong to two shores (top-right and bottom-left touch both oceans).
• Recursive DFS on a large grid can overflow the call stack; BFS or an explicit stack avoids it.

Follow-ups to expect

• What if there were k oceans instead of two? (One multi-source search per ocean.)
• What if water could also flow diagonally? (Eight neighbours, same reverse search.)
• Can you do it with a single traversal? (Store a two-bit mask per cell.)

In real software

Hydrology and GIS tools compute drainage basins from elevation maps this way, and the same reverse multi-source search finds which servers can reach both of two data centres in a network.

Practice next