FAANGPrep Sprint

Pacific Atlantic Water Flow

Find cells that can flow to both oceans.

MediumSolve on LeetCode

Examples

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

Explain:

Cells that can reach both Pacific (Top/Left) and Atlantic (Bottom/Right).

Problem Understanding

Water flows downhill (neighbor height <= current height).

Pacific Ocean: Touches Left and Top edges.
Atlantic Ocean: Touches Right and Bottom edges.

Find all coordinates (r, c) from which water can flow to BOTH oceans.

Algorithm Strategy (Backwards Flow)

Simulating flow from every cell is slow (O(MN * MN)).

Better Idea: Reverse the flow! Start from the Oceans and go uphill.

Pacific Set: Run DFS from all Top/Left edges. Store reachable cells.
Atlantic Set: Run DFS from all Bottom/Right edges. Store reachable cells.
Result: The intersection of both sets.

Visualization

NUMBERS = HEIGHTS · PACIFIC: TOP + LEFT · ATLANTIC: BOTTOM + RIGHT · GREEN = BOTH

PACIFIC — TOP ROW

Pacific

Atlantic

Both

call stack · Pacific

No dfs running

Top row (0, 0) touches the Pacific: call dfs(0, 0) with prev = its own height, 1

dfs(0, 0): height 1 ≥ 1 — it drains to the Pacific. Mark it

heights

Both oceans climb in from their edges: the Pacific from the top row and left column, the Atlantic from the bottom row and right column, in the order the code calls them. A call returns if it leaves the grid, reaches a cell this ocean already reached, or would have to go downhill. Each ocean keeps its own colour; cells both oceans reach turn green, and the last pass collects them in row order.