Pacific Atlantic Water Flow

Difficulty: Hard

Problem

An island is a grid of heights. The Pacific Ocean touches its TOP and LEFT edges; the Atlantic touches the BOTTOM and RIGHT. Rain falling on a cell flows to any 4-directional neighbor of EQUAL OR LOWER height, and eventually off the edges into the oceans. Return every cell from which water can reach BOTH oceans.

Example

Input: 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]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: From cell (2,2) with height 5, water can slide downhill north-west to the Pacific AND south-east to the Atlantic. Seven cells manage this double escape.

Brute-force approach

The per-cell simulation (O((mn)²)) is discussed and rejected inside the lesson — the reversal IS the insight being taught.

Optimal approach

Key insight: Don't chase water downhill from every cell — stand in each ocean and climb. Two multi-source floods and a set intersection replace thousands of simulations.

Flood uphill from all Pacific coast cells, then from all Atlantic coast cells. Cells reached by both floods can drain to both oceans.

Steps

  1. Collect Pacific coast cells (top row + left column) and Atlantic coast cells (bottom row + right column)
  2. Flood uphill (neighbor ≥ current) from all Pacific starts — mark the Pacific set
  3. Flood uphill from all Atlantic starts — mark the Atlantic set
  4. Return every cell in BOTH sets

Time complexity: O(rows × cols) · Space complexity: O(rows × cols)