Problem
Given anm × n matrix of heights, return a list of coordinates where water can flow to both oceans.
The Pacific Ocean touches the top and left edges of the matrix, while the Atlantic Ocean touches the bottom and right edges.
Water can flow from one cell to an adjacent cell if the adjacent cell has a height less than or equal to the current cell.
Example(s)
Consider the following example(s) to understand the expected input and output.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]
]
0 1 2 3 4
+---+---+---+---+---+
0 | 1 | 2 | 2 | 3 | 5 |
+---+---+---+---+---+
1 | 3 | 2 | 3 | 4 | 4 |
+---+---+---+---+---+
2 | 2 | 4 | 5 | 3 | 1 |
+---+---+---+---+---+
3 | 6 | 7 | 1 | 4 | 5 |
+---+---+---+---+---+
4 | 5 | 1 | 1 | 2 | 4 |
+---+---+---+---+---+
Output
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Solution
Instead of starting from every cell and checking whether water can reach both oceans, we start from the ocean borders and traverse inward.For the Pacific Ocean, DFS starts from every cell on the top and left borders. For the Atlantic Ocean, DFS starts from every cell on the bottom and right borders.
Since we are traversing in the reverse direction of water flow, we can move from the current cell to a neighboring cell only when the neighboring cell has a height greater than or equal to the current cell.
Two boolean matrices are used. The
pacific matrix stores all cells that can reach the Pacific Ocean, while the atlantic matrix stores all cells that can reach the Atlantic Ocean.
Finally, every cell marked as reachable in both matrices is added to the result.
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> list = new ArrayList<>();
int n = heights.length;
int m = heights[0].length;
boolean[][] pacific = new boolean[n][m];
boolean[][] atlantic = new boolean[n][m];
// Start DFS from the top and bottom borders.
for (int j = 0; j < m; j++) {
dfs(heights, pacific, 0, j, heights[0][j]);
dfs(heights, atlantic, n - 1, j,
heights[n - 1][j]);
}
// Start DFS from the left and right borders.
for (int i = 0; i < n; i++) {
dfs(heights, pacific, i, 0, heights[i][0]);
dfs(heights, atlantic, i, m - 1,
heights[i][m - 1]);
}
// Find cells that can reach both oceans.
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (pacific[i][j] && atlantic[i][j]) {
list.add(List.of(i, j));
}
}
}
return list;
}
private void dfs(int[][] heights, boolean[][] ocean,
int i, int j, int borderHeight) {
// Stop at boundaries, visited cells, or lower cells.
if (i < 0 || j < 0
|| i >= heights.length
|| j >= heights[0].length
|| ocean[i][j]
|| heights[i][j] < borderHeight) {
return;
}
ocean[i][j] = true;
dfs(heights, ocean, i + 1, j, heights[i][j]);
dfs(heights, ocean, i - 1, j, heights[i][j]);
dfs(heights, ocean, i, j + 1, heights[i][j]);
dfs(heights, ocean, i, j - 1, heights[i][j]);
}
}
Complexity
Each cell can be visited at most once for the Pacific traversal and once for the Atlantic traversal, resulting inO(m × n) time complexity.
The two boolean matrices require
O(m × n) space, and in the worst case, the DFS recursion stack can also contain O(m × n) cells.