Pacific Atlantic Water Flow

Problem

Hydrological modeling tools simulate water runoff across terrain. Given an m x n height matrix, water can flow from a cell to any adjacent cell with equal or lower height. The Pacific ocean touches the top and left edges; the Atlantic touches the bottom and right edges. Return all cells from which water can flow to both oceans.

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]]

Solution

Approach: Reverse multi-source BFS from each ocean's border, then intersect the two reachable sets.

The naive idea - simulate water flowing downhill from every cell and check if it reaches each ocean - repeats work and costs O(mn(m+n)). Reverse the direction instead: start at the ocean and ask which cells can drain into it. Water flows to equal-or-lower neighbors, so reversing means we climb - from a border cell we step to a neighbor only when heights[neighbor] >= heights[current]. Seed one BFS with every Pacific border cell (top row plus left column) and another with every Atlantic border cell (bottom row plus right column); each is a multi-source BFS where all sources start enqueued and pre-marked visited. Each pass returns the set of cells that can reach that ocean. The answer is the intersection pacific_reachable & atlantic_reachable - cells that drain to both. Marking a cell visited on enqueue (not dequeue) keeps each cell enqueued at most once per pass, holding the work to O(m*n). The whole grid is swept exactly twice rather than once per source cell, which is the win over forward simulation.

Edge cases: Empty grid returns []. A 1x1 grid is both a Pacific and Atlantic border cell, so it lands in both sets. A flat grid (all equal heights) lets BFS spread everywhere from both borders, so every cell is in the answer. Corner cells sit on two borders and trivially reach their adjacent ocean.

Complexity: O(m * n) time, O(m * n) space - two BFS passes each enqueue every cell at most once; the two reachable sets and queues are O(m * n).