Browse Curriculum
FAANGPrep Sprint
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 / 1
Visualization data missing
Initializing...
1x
Blue waves from Top-Left, Green waves from Bottom-Right. Result is where they crash.
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.