Given an m x n matrix of heights representing an island, water can flow from a cell to its adjacent cells (up, down, left, right) if the adjacent cell's height is less than or equal to the current cell's height. The Pacific ocean borders the top and left edges, and the Atlantic ocean borders the bottom and right edges.
Find all cells from which water can flow to both the Pacific and Atlantic oceans.
For example:
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
Cells that can reach both oceans include: (0,4), (1,3), (1,4), (2,2), (3,0), (3,1), (4,0)
A naive approach would check every cell to see if it can reach both oceans. How can you do better?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
Instead of checking from every cell outward, think in reverse: start from the ocean borders and work inward.
- Hint 2
Run BFS/DFS from all Pacific border cells to find which cells can reach the Pacific. Do the same from Atlantic border cells.
- Hint 3
The answer is the intersection of both sets: cells reachable from both oceans (flowing uphill from the ocean).
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.