Pacific Atlantic Water Flow
The problem
In a rectangular height grid, water may move to a horizontal or vertical neighbor of equal or lower height. Return cells that can reach both the top/left boundary and the bottom/right boundary.
Example
In a 2×2 grid of equal heights, all four cells reach both boundaries.
Need a hint?
Reverse the flow and start from each boundary.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Run a multi-source traversal from the top and left edges, moving only to equal or higher neighbors. Separately do the same from the bottom and right edges. A cell reaches both oceans exactly when it belongs to both visited sets.
Complexity
O(mn) time and O(mn) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.