MEDIUM NC#83 Blind #29 Graphs / DFS
417. Pacific Atlantic Water Flow
📖 Problem
There is an m x n rectangular island that borders both the Pacific and Atlantic oceans. The Pacific Ocean touches the left and top edges of the island, and the Atlantic Ocean touches the right and bottom edges of the island. Return a 2D list of grid coordinates result[i] such that result[i].length = 2, and result[i][0] lists all coordinates (r, c) of cells where rain water can flow to both the Pacific and Atlantic oceans.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •Recursive stack flow
- •Cycle prevention
- •Post-order reasoning
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply DFS reasoning pattern
💡 Approach
- → For Pacific: flow to top and left edges
- → For Atlantic: flow to bottom and right edges
- → Use DFS from each border cell
- → Track cells that can reach each ocean
- → Time: O(m * n), Space: O(m * n)
🧭 Prerequisites
🛠️ Hints & Pitfalls
Hints
- •For Pacific: flow to top and left edges
- •For Atlantic: flow to bottom and right edges
- •Use DFS from each border cell
Common Pitfalls
- •Track cells that can reach each ocean
- •Time: O(m * n), Space: O(m * n)
🧪 Test Cases
Test Case 1
Not run Input:
pacificAtlantic(heights: number[][]); Expected:
Computed from hidden reference Test Case 2
Not run Input:
pacificAtlantic([[1,2,2,3,4],[3,2,2,3,0,1],[2,3,1,2,4,1,5],[3,2,2,3,0,0,3,2,4,1]]); Expected:
Computed from hidden reference Test Case 3
Not run Input:
pacificAtlantic([[2,1],[2,2,1],[3,2,4,1],[3,2,2,4,1,3,2,4,1]]); Expected:
Computed from hidden reference 📝 Code Editor
📤 Output