Practice Pacific Atlantic Water Flow
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Pacific Atlantic Water Flow
Problem Statement
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean. Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Source: Pacific Atlantic Water Flow on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
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]]
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
# Example 2
heights = [[1]]
[[0,0]]
Constraints
How to solve Pacific Atlantic Water Flow
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Reverse the flow: start from each ocean's border cells and climb to neighbors of equal or greater height. A cell can drain to an ocean exactly when that ocean's reverse climb reaches it, so two traversals and an intersection answer every cell at once.
Why brute force is not enough
Run a separate downhill search from every cell and record whether it touches the top-or-left border and the right-or-bottom border. Each search can visit all mn cells, so the total is O((mn)^2); with m and n up to 200 that is roughly 1.6 times 10^9 cell visits.
Approach
- Create two boolean grids, one marking cells that can drain to the Pacific and one for the Atlantic.
- Seed the Pacific search with every cell in the top row and left column, and the Atlantic search with every cell in the bottom row and right column; border cells drain directly into the adjacent ocean.
- From each seed, run DFS or BFS that moves to a four-directional neighbor only if its height is greater than or equal to the current height and it is not yet marked. This is the exact reverse of the downhill rule, so the invariant is that every marked cell can send water to that ocean.
- After both traversals, scan the grid once and collect every coordinate marked in both grids.
Walkthrough of Example 1
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]] → [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
- The Pacific climb starts from row 0 and column 0. From (0,1) at height 2 it reaches (1,1) at 2, then (1,2) at 3, (2,2) at 5, and (1,3) at 4, which reaches (1,4) at 4; from (3,0) at 6 it reaches (3,1) at 7.
- The Atlantic climb starts from row 4 and column 4. From (1,4) it reaches (1,3); from (2,4) at 1 it reaches (2,3) at 3 and then (2,2) at 5; from (4,0) at 5 it reaches (3,0) at 6; from (4,1) at 1 it reaches (3,1) at 7.
- Intersecting the two marked sets leaves (0,4), (1,3), (1,4), (2,2), (3,0), (3,1), and (4,0).
- Listed in row-major order these form exactly the expected output.
Time and space
Time O(mn) · Space O(mn). Each traversal marks every cell at most once and inspects four neighbors; the two boolean grids plus the stack or queue hold at most mn entries, where m and n are the grid dimensions.
Interview pitfalls
- Using strictly greater than when climbing; equal heights must be allowed because water flows between equal neighbors.
- Forgetting that the corners (0, n-1) and (m-1, 0) belong to both oceans and must be seeded into both searches.
- Recursive DFS on a 200 by 200 grid can reach a depth of 40,000 frames and overflow the stack in some languages; use an explicit stack or BFS.
- Marking a cell visited only when it is popped rather than when it is pushed, which lets the queue hold duplicates.
Follow-up questions interviewers ask
- How would you count the cells that can reach at least one ocean rather than both?
- If heights could change over time, how would you update the answer incrementally instead of recomputing both traversals?
Further reading on the technique: Depth-first search
Related LeetCode Problems
Practice more problems similar to Pacific Atlantic Water Flow.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.