mediumGraphsGraphs

Pacific Atlantic Water Flow

mediumTime: O(m*n)Space: O(m*n)

Recognize the pattern

water flows to both oceanswhich cells reach bothreverse the flow direction

Brute force idea

If you approach Pacific Atlantic Water Flow in the most literal way possible, you get this: For each cell, DFS/BFS to check if water can reach both oceans. Each cell's reachability is computed independently. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

Better approach

A calmer way to see Pacific Atlantic Water Flow is this: Reverse thinking: start from ocean borders and flow uphill. DFS/BFS from Pacific border marks all cells that can reach Pacific. Same from Atlantic border. Intersection of both sets is the answer. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Key invariant

The truth you want to protect throughout Pacific Atlantic Water Flow is this: Instead of asking 'can this cell reach the ocean?' (flows downhill), ask 'can the ocean reach this cell?' (flows uphill from the border). The answer is the same, but starting from borders is much more efficient. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Watch out for

One easy way to drift off course in Pacific Atlantic Water Flow is this: Flowing downhill from each cell — that's the natural direction but leads to worst case. Reversing to flow uphill from the borders reduces it to two passes. The fix is usually to return to the meaning of each move, not just the steps themselves.

Graphs Pattern