Water flows from a cell to a neighbor of equal or lower height. The Pacific touches the top and left edges and the Atlantic the bottom and right. Return every cell from which water can reach both oceans.
Before you code
Searching downhill from every cell repeats the same exploration many times. Reverse it: from each ocean, search uphill (to equal or higher neighbors). Each search marks every cell that drains into that ocean.
Hints
- Start one DFS or BFS from all Pacific border cells and one from all Atlantic border cells.
- Move to a neighbor only if its height is at least the current cell's.
- The answer is the cells marked by both searches. Total O(rows × columns).
Production & complexity notes
When solving Pacific Atlantic water flow on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Depth-first search to reinforce the underlying pattern.
What it practices
Reversing the direction of a search, from Depth-first search.