Pacific Atlantic Water Flow

Find cells whose water can reach both oceans.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Pacific Atlantic Water Flow: Reverse both flow searches from their ocean borders, move uphill, then intersect the reached cells.

Input and goalFind cells whose water can reach both oceans.

Seed the Pacific reverse searchPacific starts are every top- or left-border cell: (0,0),(0,1),(0,2),(1,0),(2,0). These five cells initialize seen and the stack.

1P seed2P seed2P seed3P seed232P seed41

input3x3 heights; top/left=P, bottom/right=AsearchPacificstack5 border seedsreached5 cells

Recognize it

Many grid cells ask whether they can reach either of two fixed boundary goals; reversing the edges lets each goal share one traversal across all possible starts.

Keep true

Each ocean’s seen set contains exactly cells with a nonincreasing forward path to that ocean. Reverse traversal may move only to an equal-or-higher neighbor, preserving that path witness.

Reuse it

When many sources query reachability to a small set of goals, reverse the graph, traverse once from each goal class, and combine the resulting reachable sets.

Pattern: Reverse graph search from both goals.

Simple idea: Searching from every cell repeats work. Start from each ocean instead. Move uphill or across equal height, which is the reverse of water flow. Intersect the two reached sets.

def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
   if not heights or not heights[0]:
      return []

   rows, cols = len(heights), len(heights[0])

   def reachable(starts: set[tuple[int, int]]) -> set[tuple[int, int]]:
      seen = set(starts)
      stack = list(starts)
      while stack:
         row, col = stack.pop()
         for row_step, col_step in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_cell = row + row_step, col + col_step
            next_row, next_col = next_cell
            if not (0 <= next_row < rows and 0 <= next_col < cols):
               continue
            if next_cell in seen or heights[next_row][next_col] < heights[row][col]:
               continue
            seen.add(next_cell)
            stack.append(next_cell)
      return seen

   pacific = {(row, 0) for row in range(rows)} | {(0, col) for col in range(cols)}
   atlantic = {(row, cols - 1) for row in range(rows)} | {
      (rows - 1, col) for col in range(cols)
   }
   return [list(cell) for cell in sorted(reachable(pacific) & reachable(atlantic))]

Cost: $O(rows\times cols)$ time and space.