[Medium] 417. Pacific Atlantic Water Flow
There is an m x n rectangular island that borders both the Pacific Ocean and the 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.
Examples
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 are the cells where water can flow to both Pacific and Atlantic oceans:
- [0,4]: Water flows from [0,4] to Pacific Ocean
- [1,3]: Water flows from [1,3] to Pacific Ocean
- [1,4]: Water flows from [1,4] to Pacific Ocean
- [2,2]: Water flows from [2,2] to Pacific Ocean
- [3,0]: Water flows from [3,0] to Pacific Ocean
- [3,1]: Water flows from [3,1] to Pacific Ocean
- [4,0]: Water flows from [4,0] to Pacific Ocean
Example 2:
Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]
Explanation: All cells can flow to both Pacific and Atlantic oceans.
Constraints
m == heights.lengthn == heights[i].length1 <= m, n <= 2000 <= heights[i][j] <= 10^5
Thinking Process
- Instead of checking if each cell can reach oceans
- Visited tracking: Prevents infinite loops
- Model entities as nodes and relationships as edges.
- Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
- Union-Find helps when connectivity updates are frequent.
Common Approaches
Typical techniques for this pattern:
| Approach | Time | Space | Notes |
|---|---|---|---|
| Recursive DFS (this problem) | O(n) | O(h) stack | Natural for trees and graphs |
| Iterative DFS (stack) | O(n) | O(n) | Avoid recursion depth limits |
| DFS with memoization | O(n) | O(n) | Overlapping subproblems on graphs |
| Backtracking DFS | O(2^n) typical | O(n) | Enumerate choices with pruning |
Solution
Time Complexity: O(m × n) where m and n are dimensions of the grid
Space Complexity: O(m × n) for visited arrays and recursion stack
Use DFS from Pacific and Atlantic ocean boundaries to find all cells that can reach each ocean, then find the intersection.
class Solution {
int m, n;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
public void dfs(int[][] heights, boolean[][]& visited, int row, int col) {
visited[row][col] = true;
for (int dir : dirs) {
int newRow = row + dir[0], newCol = col + dir[1];
if(newRow < 0 || newRow >= m || newCol < 0 || newCol >= n) continue;
if(visited[newRow][newCol] || heights[row][col] > heights[newRow][newCol]) continue;
dfs(heights, visited, newRow, newCol);
}
}
int[][] pacificAtlantic(int[][] heights) {
m = heights.length, n = heights[0].length;
boolean[][] pacific(m, boolean[](n, false));
boolean[][] atlantic(m, boolean[](n, false));
// DFS from Pacific Ocean boundaries (left and top edges)
for(int i = 0; i < m; i++) dfs(heights, pacific, i, 0);
for(int j = 0; j < n; j++) dfs(heights, pacific, 0, j);
// DFS from Atlantic Ocean boundaries (right and bottom edges)
for(int i = m - 1; i >= 0; i--) dfs(heights, atlantic, i, n - 1);
for(int j = n - 1; j >= 0; j--) dfs(heights, atlantic, m - 1, j);
// Find cells that can reach both oceans
List<int[]> rtn = new ArrayList<>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(pacific[i][j] && atlantic[i][j]) {
rtn.add(new int[] {i, j});
}
}
}
return rtn;
}
}
Solution Explanation
Key Insight: Instead of checking if each cell can reach both oceans, start from ocean boundaries and find all reachable cells.
Steps:
- Create visited arrays for Pacific and Atlantic oceans
- DFS from Pacific boundaries:
- Left edge:
(i, 0)for all rows - Top edge:
(0, j)for all columns
- Left edge:
- DFS from Atlantic boundaries:
- Right edge:
(i, n-1)for all rows - Bottom edge:
(m-1, j)for all columns
- Right edge:
- Find intersection: Cells that can reach both oceans
- Return result as list of coordinates
Step-by-Step Example
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]]
Step 1: DFS from Pacific Ocean boundaries
Pacific boundaries (left and top edges):
- Left edge:
(0,0), (1,0), (2,0), (3,0), (4,0) - Top edge:
(0,0), (0,1), (0,2), (0,3), (0,4)
DFS from Pacific boundaries:
Pacific reachable cells:
[0,0] → [0,1] → [0,2] → [0,3] → [0,4]
[1,0] → [1,1] → [1,2] → [1,3] → [1,4]
[2,0] → [2,1] → [2,2] → [2,3] → [2,4]
[3,0] → [3,1] → [3,2] → [3,3] → [3,4]
[4,0] → [4,1] → [4,2] → [4,3] → [4,4]
Step 2: DFS from Atlantic Ocean boundaries
Atlantic boundaries (right and bottom edges):
- Right edge:
(0,4), (1,4), (2,4), (3,4), (4,4) - Bottom edge:
(4,0), (4,1), (4,2), (4,3), (4,4)
DFS from Atlantic boundaries:
Atlantic reachable cells:
[0,4] → [0,3] → [0,2] → [0,1] → [0,0]
[1,4] → [1,3] → [1,2] → [1,1] → [1,0]
[2,4] → [2,3] → [2,2] → [2,1] → [2,0]
[3,4] → [3,3] → [3,2] → [3,1] → [3,0]
[4,4] → [4,3] → [4,2] → [4,1] → [4,0]
Step 3: Find intersection
Cells that can reach both oceans:
[0,4]: Can reach Pacific and Atlantic[1,3]: Can reach Pacific and Atlantic[1,4]: Can reach Pacific and Atlantic[2,2]: Can reach Pacific and Atlantic[3,0]: Can reach Pacific and Atlantic[3,1]: Can reach Pacific and Atlantic[4,0]: Can reach Pacific and Atlantic
Final result: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Algorithm Breakdown
DFS Function:
class Solution {
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
public void bfs(int[][] heights, boolean[][]& visited, queue<int[]>& q) {
while(!q.isEmpty()) {
auto [row, col] = q.get(0);
q.poll();
for (int dir : dirs) {
int newRow = row + dir[0], newCol = col + dir[1];
if(newRow < 0 || newRow >= heights.length || newCol < 0 || newCol >= heights[0].length) continue;
if(visited[newRow][newCol] || heights[row][col] > heights[newRow][newCol]) continue;
visited[newRow][newCol] = true;
q.offer(new int[] {newRow, newCol});
}
}
}
int[][] pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
boolean[][] pacific(m, boolean[](n, false));
boolean[][] atlantic(m, boolean[](n, false));
queue<int[]> pacificQ, atlanticQ;
// Add Pacific boundaries
for(int i = 0; i < m; i++) {
pacificQ.offer(new int[] {i, 0});
pacific[i][0] = true;
}
for(int j = 0; j < n; j++) {
pacificQ.offer(new int[] {0, j});
pacific[0][j] = true;
}
// Add Atlantic boundaries
for(int i = 0; i < m; i++) {
atlanticQ.offer({i, n-1});
atlantic[i][n-1] = true;
}
for(int j = 0; j < n; j++) {
atlanticQ.offer({m-1, j});
atlantic[m-1][j] = true;
}
bfs(heights, pacific, pacificQ);
bfs(heights, atlantic, atlanticQ);
List<int[]> result = new ArrayList<>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(pacific[i][j] && atlantic[i][j]) {
result.add(new int[] {i, j});
}
}
}
return result;
}
}
Process:
- Mark current cell as visited
- Check all 4 directions (up, down, left, right)
- Skip invalid cells (out of bounds, already visited)
- Skip higher cells (water can’t flow uphill)
- Recursively visit reachable cells
Boundary DFS:
class Solution {
List<Integer> parent = new ArrayList<>();
List<Integer> rank = new ArrayList<>();
public int find(int x) {
if(parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void unite(int x, int y) {
int px = find(x), py = find(y);
if(px == py) return;
if(rank[px] < rank[py]) {
parent[px] = py;
} else if(rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank.put(px, rank.getOrDefault(px, 0) + 1);
}
}
int[][] pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
int total = m n;
parent.resize(total);
rank.resize(total, 0);
iota(parent /* elements of parent */, 0);
// Connect cells that can flow to each other
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int curr = i n + j;
if(i > 0 && heights[i][j] >= heights[i-1][j]) {
unite(curr, (i-1) * n + j);
}
if(j > 0 && heights[i][j] >= heights[i][j-1]) {
unite(curr, i n + (j-1));
}
}
}
// Find cells that can reach both oceans
List<int[]> result = new ArrayList<>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int curr = i n + j;
boolean canReachPacific = false, canReachAtlantic = false;
// Check if can reach Pacific
for(int k = 0; k < m; k++) {
if(find(curr) == find(k n + 0)) {
canReachPacific = true;
break;
}
}
for(int k = 0; k < n; k++) {
if(find(curr) == find(0 n + k)) {
canReachPacific = true;
break;
}
}
// Check if can reach Atlantic
for(int k = 0; k < m; k++) {
if(find(curr) == find(k n + (n-1))) {
canReachAtlantic = true;
break;
}
}
for(int k = 0; k < n; k++) {
if(find(curr) == find((m-1) * n + k)) {
canReachAtlantic = true;
break;
}
}
if(canReachPacific && canReachAtlantic) {
result.add(new int[] {i, j});
}
}
}
return result;
}
}
Process:
- Pacific boundaries: Left edge and top edge
- Atlantic boundaries: Right edge and bottom edge
- DFS from each boundary to find reachable cells
- Mark visited cells in respective arrays
Complexity
| Operation | Time Complexity | Space Complexity | |———–|—————-|——————| | Pacific DFS | O(m × n) | O(m × n) | | Atlantic DFS | O(m × n) | O(m × n) | | Intersection | O(m × n) | O(1) | | Total | O(m × n) | O(m × n) |
Where m and n are the dimensions of the grid.
Detailed Example Walkthrough
Example: heights = [[2,1],[1,2]]
Step 1: Pacific boundaries
- Left edge:
(0,0), (1,0) - Top edge:
(0,0), (0,1)
Pacific DFS:
[0,0] → [0,1] → [1,1]
[1,0] → [1,1]
Step 2: Atlantic boundaries
- Right edge:
(0,1), (1,1) - Bottom edge:
(1,0), (1,1)
Atlantic DFS:
[0,1] → [0,0] → [1,0]
[1,1] → [1,0]
Step 3: Intersection All cells can reach both oceans:
[0,0]: Pacific ✓, Atlantic ✓[0,1]: Pacific ✓, Atlantic ✓[1,0]: Pacific ✓, Atlantic ✓[1,1]: Pacific ✓, Atlantic ✓
Final result: [[0,0],[0,1],[1,0],[1,1]]
Common Mistakes
- Single cell:
heights = [[5]]→[[0,0]] - All same height:
heights = [[1,1],[1,1]]→[[0,0],[0,1],[1,0],[1,1]] - Increasing heights:
heights = [[1,2],[3,4]]→[[0,0],[0,1],[1,0],[1,1]] -
Decreasing heights:
heights = [[4,3],[2,1]]→[[0,0],[0,1],[1,0],[1,1]] - Wrong direction: Starting from each cell instead of ocean boundaries
- Missing boundary cells: Not including all boundary cells in DFS
- Incorrect height check: Not handling equal heights correctly
- Out of bounds: Not checking array bounds properly
Related Problems
Why This Solution Works
Reverse Thinking:
- Instead of checking if each cell can reach oceans
- Start from ocean boundaries and find reachable cells
- Much more efficient than checking each cell individually
- O(m × n) complexity instead of O(m² × n²)
DFS Properties:
- Visited tracking: Prevents infinite loops
- Boundary checking: Ensures valid coordinates
- Height constraint: Water flows downhill or level
- Recursive exploration: Finds all reachable cells
Key Algorithm Properties:
- Correctness: Always produces valid result
- Optimality: Produces correct ocean reachability
- Efficiency: O(m × n) time complexity
- Simplicity: Easy to understand and implement
References
- LC 417: Pacific Atlantic Water Flow on LeetCode
- LeetCode Discuss — LC 417: Pacific Atlantic Water Flow
- LeetCode Editorial (may require premium)
Key Takeaways
Reverse Thinking:
- Instead of checking if each cell can reach oceans
- Start from ocean boundaries and find reachable cells
- Much more efficient than checking each cell individually
- O(m × n) complexity instead of O(m² × n²)
DFS Properties:
- Visited tracking: Prevents infinite loops
- Boundary checking: Ensures valid coordinates
- Height constraint: Water flows downhill or level
- Recursive exploration: Finds all reachable cells