Watch 10 video solutions for Pacific Atlantic Water Flow, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 281,442 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
[0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
[1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
[1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
[2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
[3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
[3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]] Output: [[0,0]] Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105Problem Overview: You are given an m x n height matrix where water can flow from a cell to neighboring cells with equal or lower height. The Pacific touches the left and top edges, and the Atlantic touches the right and bottom edges. Return all coordinates where water can flow to both oceans.
Approach 1: Depth-First Search (DFS) from Ocean Borders (O(m*n) time, O(m*n) space)
The key insight is to reverse the thinking. Instead of starting from every cell and checking if water reaches an ocean, start DFS from the ocean borders and move inward. From each ocean edge, run DFS to neighbors with height >= current. This simulates water flowing in reverse. Maintain two visited matrices: one for Pacific reachability and one for Atlantic reachability. After DFS completes, iterate through the grid and collect cells reachable from both. This approach uses recursion and works naturally with grid traversal problems involving depth-first search on a matrix.
Approach 2: Breadth-First Search (BFS) Multi-Source Traversal (O(m*n) time, O(m*n) space)
This approach applies the same reverse-flow insight but replaces recursion with queues. Initialize two BFS queues with all Pacific border cells and Atlantic border cells respectively. Perform BFS while only moving to neighbors with height greater than or equal to the current cell. Track visited cells for each ocean using boolean grids. Once both traversals finish, scan the grid and add coordinates that appear in both visited sets. BFS avoids recursion depth limits and is often preferred when implementing graph traversal on large grids using breadth-first search.
Recommended for interviews: Interviewers expect the reverse traversal idea with DFS or BFS. A brute force approach (checking reachability from every cell) shows initial reasoning but runs in O((m*n)^2). The multi-source DFS/BFS solution reduces it to O(m*n) and demonstrates strong understanding of graph traversal on a grid and how to flip the search direction to avoid redundant work.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS from Ocean Borders | O(m*n) | O(m*n) | Clean recursive solution when stack depth is manageable and DFS is comfortable to implement |
| BFS Multi-Source Traversal | O(m*n) | O(m*n) | Preferred for iterative implementations or when avoiding recursion limits on large grids |