Depth-First Search
Medium
Pacific Atlantic Water Flow
Find cells that can flow to both oceans.
10 min read
Solve on LeetCodeExamples
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
Step 1 / 18
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
Problem: Find cells that can flow to both Pacific (Top/Left) and Atlantic (Right/Bottom) oceans. Flow is from High -> Low/Equal.
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.