Pacific Atlantic Water Flow
You are given an m × n matrix of heights.
Water can flow from one cell to another if:
height[next] <= height[current]
Water can move in four directions:
up
down
left
right
The Pacific Ocean touches:
- Top row
- Left column
The Atlantic Ocean touches:
- Bottom row
- Right column
Return all cells from which water can flow to both oceans.
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]
]
The cells that can reach both oceans include:
[0,4]
[1,3]
[1,4]
[2,2]
[3,0]
[3,1]
[4,0]
Main Idea
A direct approach would start DFS from every cell and check whether it can reach both oceans.
That can be expensive.
Instead, reverse the direction of the search.
Normally water flows:
high → low
So when searching backward from an ocean, we can move from:
low → high
Approach
Run DFS/BFS twice.
Pacific DFS
Start from every cell touching the Pacific:
Top row
Left column
Mark every cell that can eventually reach the Pacific.
Atlantic DFS
Start from:
Bottom row
Right column
Mark every cell that can reach the Atlantic.
Finally, return cells that are marked in both searches.
Pacific Reachable ∩ Atlantic Reachable = Answer
Example 1
Input
5 5 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
Explanation
For example, cell:
[0,4]
has height 5.
It can reach the Pacific through the top edge and the Atlantic through the right edge.
Similarly, all returned cells have paths to both oceans.
Example 2
Input
1 1 10
Output
0 0
Explanation
The only cell touches both oceans because it is simultaneously:
Top + Bottom
Left + Right
Therefore, it can reach both oceans.
Constraints
Hints:
Hint 1
Instead of asking:
Can water flow from this cell to an ocean?
Reverse the question:
Which cells can be reached when starting from an ocean?
Hint 2
For the Pacific Ocean, start DFS/BFS from:
Top row
Left column
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 16, 2026
Last updated
Aug 18, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output