Given an m x n matrix of heights representing an island, where 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 oceans. Water can flow from a cell to any adjacent cell (up, down, left, right) with equal or lower height. Return a list of [row, col] coordinates for all such cells.
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]
]
Output: [[0,4], [1,3], [1,4], [2,2], [3,0], [3,1], [4,0]]
For example, cell (2,2) with height 5 can reach the Pacific (top/left edges) because water flows downhill through cells to the top or left, and can also reach the Atlantic (bottom/right edges) through cells to the bottom or right. Only these 7 cells can drain to both oceans.
Instead of checking from every cell which ocean it can reach, think in reverse — start from the ocean edges and flow inward to higher-or-equal cells using DFS/BFS. Do this separately for Pacific (top and left edges) and Atlantic (bottom and right edges). The answer is every cell reachable from both oceans.
Why this works
Instead of checking each cell to see if water can flow to both oceans (expensive), reverse the problem: start from each ocean’s border and “flow uphill” to find all cells that can drain into that ocean. A cell in both the Pacific-reachable set and the Atlantic-reachable set can drain into both oceans.
Step by step
- Create two visited sets — one for cells reachable from the Pacific, one for the Atlantic.
- Seed DFS from Pacific borders — start DFS from every cell on the top row and left column.
- Seed DFS from Atlantic borders — start DFS from every cell on the bottom row and right column.
- Flow uphill — in each DFS, move to neighboring cells only if their height is greater than or equal to the current cell (reverse of water flowing downhill).
- Intersect the two sets — any cell marked in both sets can reach both oceans.
Time: O(m×n)
Space: O(m×n)
class Solution {
private int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int rows = heights.length, cols = heights[0].length;
boolean[][] pacific = new boolean[rows][cols];
boolean[][] atlantic = new boolean[rows][cols];
for (int c = 0; c < cols; c++) { // seed DFS from top and bottom edges
dfs(heights, pacific, 0, c, heights[0][c]);
dfs(heights, atlantic, rows - 1, c, heights[rows - 1][c]);
}
for (int r = 0; r < rows; r++) { // seed DFS from left and right edges
dfs(heights, pacific, r, 0, heights[r][0]);
dfs(heights, atlantic, r, cols - 1, heights[r][cols - 1]);
}
List<List<Integer>> result = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (pacific[r][c] && atlantic[r][c]) { // reachable from both oceans
result.add(List.of(r, c));
}
}
}
return result;
}
private void dfs(int[][] heights, boolean[][] reachable, int r, int c, int prevHeight) {
if (r < 0 || r >= heights.length || c < 0 || c >= heights[0].length
|| reachable[r][c] || heights[r][c] < prevHeight) {
return; // out of bounds, visited, or water can't flow uphill to here
}
reachable[r][c] = true; // mark this cell as reachable from this ocean
for (int[] dir : directions) {
dfs(heights, reachable, r + dir[0], c + dir[1], heights[r][c]);
}
}
}
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int rows = heights.size(), cols = heights[0].size();
vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
for (int c = 0; c < cols; c++) { // seed DFS from top and bottom edges
dfs(heights, pacific, 0, c, heights[0][c]);
dfs(heights, atlantic, rows - 1, c, heights[rows - 1][c]);
}
for (int r = 0; r < rows; r++) { // seed DFS from left and right edges
dfs(heights, pacific, r, 0, heights[r][0]);
dfs(heights, atlantic, r, cols - 1, heights[r][cols - 1]);
}
vector<vector<int>> result;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (pacific[r][c] && atlantic[r][c]) { // reachable from both oceans
result.push_back({r, c});
}
}
}
return result;
}
private:
void dfs(vector<vector<int>>& heights, vector<vector<bool>>& reachable,
int r, int c, int prevHeight) {
if (r < 0 || r >= heights.size() || c < 0 || c >= heights[0].size()
|| reachable[r][c] || heights[r][c] < prevHeight) {
return; // out of bounds, visited, or water can't flow uphill to here
}
reachable[r][c] = true; // mark this cell as reachable from this ocean
int dirs[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto& dir : dirs) {
dfs(heights, reachable, r + dir[0], c + dir[1], heights[r][c]);
}
}
};
def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
if not heights:
return []
rows, cols = len(heights), len(heights[0])
pacific = set()
atlantic = set()
def dfs(r, c, reachable, prev_height):
if (r < 0 or r >= rows or c < 0 or c >= cols
or (r, c) in reachable or heights[r][c] < prev_height):
return # out of bounds, visited, or water can't flow uphill to here
reachable.add((r, c)) # mark this cell as reachable from this ocean
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
dfs(r + dr, c + dc, reachable, heights[r][c])
for c in range(cols): # seed DFS from ocean borders
dfs(0, c, pacific, heights[0][c])
dfs(rows - 1, c, atlantic, heights[rows - 1][c])
for r in range(rows):
dfs(r, 0, pacific, heights[r][0])
dfs(r, cols - 1, atlantic, heights[r][cols - 1])
return [[r, c] for r, c in pacific & atlantic] # cells reachable from both oceans