Pacific Atlantic Water Flow

Difficulty: Hard

Problem

You are handed a rectangular grid of terrain heights for an island. The Pacific Ocean borders its TOP and LEFT sides, and the Atlantic borders its BOTTOM and RIGHT sides. Water on any cell can move up, down, left, or right onto a neighbor whose height is the same or lower, and any water that reaches an edge cell drains into the ocean next to it. Return every cell from which water can drain into BOTH oceans.

Example

Input: heights = [[1,3,2],[4,2,5],[3,6,1]]
Output: [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]
Explanation: Take cell (1,2) with height 5: it sits on the right edge (Atlantic) and can also step down to the top-edge cell (0,2) (Pacific). Six cells manage this double escape; only (0,0), (1,1) and (2,2) cannot.

Brute-force approach

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

Time complexity: O((mn)²) · Space complexity: O(mn)

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

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

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

Pseudocode

function pacificAtlantic(heights):
    function climb(starts):
        reached = set(starts)
        stack = starts
        while stack not empty:
            (r, c) = stack.pop()
            for each neighbor (nr, nc):
                if (nr, nc) not in reached and
                   heights[nr][nc] ____ heights[r][c]:
                    reached.add((nr, nc))
                    stack.push((nr, nc))
        return reached
    
    pacific  = climb(____ row + ____ column)
    atlantic = climb(bottom row + right column)
    
    return cells in pacific ____ atlantic

Hints

We search BACKWARDS from the ocean, flip the flow comparison. Which way?
The Pacific touches two of the four coastlines, which two?
Both floods use the exact same climb; only the starting cells differ
Drains to BOTH oceans: which set operation?

Complexity questions

What is the time complexity of the two-flood solution?

O(mn): each flood visits a cell at most once, and there are exactly two floods. Each climb marks a cell once and never returns. Two climbs + one intersection pass = O(mn). The naive per-cell version was O((mn)²): the reversal bought a full factor of mn.

What is the space complexity?

O(mn): two reached sets plus the flood stack. Each reached set can hold up to all mn cells; the stack likewise in the worst case.

Why must the WHOLE coastline seed each flood, not just a corner?

Different cells drain to different parts of the coast. A cell might reach the ocean only through the middle of the top row; seeding everything covers every entry point. The ocean is reachable through ANY coast cell. A flood from just (0,0) climbs only what's reachable uphill from there. Cells draining through, say, (0,3) would be missed entirely.

'From how many cells can water reach cell X?'. How would you apply this lesson's trick?

One reverse flood FROM X, climbing uphill: everything reached could drain to X. Same reversal, single destination: climb ≥ uphill from X, count the marked cells. When 'many sources, one destination' shows up, flip it to 'one source, walked backwards'.

Check your understanding of Pacific Atlantic Water Flow

Which direction does water flow between neighboring cells?

From a cell to any neighbor of EQUAL OR LOWER height. Water flows downhill, and also across flat ground: a neighbor with height ≤ mine is reachable. The 'or equal' matters; plateaus conduct water.

The naive plan: from EVERY cell, run a flood to see which oceans it reaches. Why is that expensive?

Each flood costs O(mn), and running one per cell gives O((mn)²), 10⁸ operations on a 100×100 grid. mn cells × O(mn) per flood = O(m²n²). The whole art of this problem is escaping that quadratic blowup.

The reversal trick: instead of asking 'where does each cell's water GO?', we ask...

'Which cells could drain INTO each ocean?'. Flood UPHILL from the coasts, marking everything that can reach that ocean. Walk the flow backwards: start at an ocean's coastline and climb to neighbors of EQUAL OR GREATER height. Every cell you can climb to could have drained down to where you came from. Two floods replace mn floods.

Why does climbing use 'neighbor height ≥ current height'?

It's the exact reverse of the flow rule: water goes high→low(or equal), so tracing backwards goes low→high(or equal). Same edges, opposite direction. If water can flow A → B (B ≤ A), then walking backwards from B we may step to A (A ≥ B). Every downhill path is discovered by an uphill walk from its destination.

After the two floods (Pacific-reachable set, Atlantic-reachable set), the answer is...

Their INTERSECTION: cells present in both sets drain to both oceans. Pacific's flood marks 'can drain to Pacific'; Atlantic's marks 'can drain to Atlantic'. Cells wearing BOTH marks answer the question. A set intersection finishes the job.