Pacific Atlantic Water Flow
Find the grid cells from which rain water can flow to both the Pacific and the Atlantic ocean.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Reverse the flow: search uphill from the cells bordering each ocean, then return the cells reached from both sides.
Pattern: Graphs. Model the problem as nodes and edges, then pick the traversal: DFS, BFS or a topological order.
Complexity
| Measure | Bound |
|---|---|
| Time | O(m · n) |
| Extra space | O(m · n) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.