Simple idea:
// 0 not visited
// 1 pacific
// 2 atlantic
// 3 both

DFS from first row and first column and mark all the reachable nodes (reverse comparison) as
1
.
If cell is marked as1
or3
already, break DFS
If cell is marked as2
already, mark it3

DFS from last row and last column and mark all the reachable nodes (reverse comparison) as
2
.
If cell is marked as2
or3
already, break DFS
If cell is marked as1
already, mark it3
 Space complexity:
O(n)
 Time complexity:
O(n^3)
I guess we can argue that it isO(n^2)
since we don't visit all then^2
cells for the4n
DFSes
public class Solution {
int m;
int n;
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new ArrayList<>();
m = matrix.length;
if (m == 0) return res;
n = matrix[0].length;
if (n == 0) return res;
// 0 not visited
// 1 pacific
// 2 atlantic
// 3 both
int[][] touchdown = new int[m][n];
for (int i = 0; i < m; ++i) {
dfs(matrix, touchdown, i, 0, 1, res);
dfs(matrix, touchdown, i, n  1, 2, res);
}
for (int j = 0; j < n; ++j) {
dfs(matrix, touchdown, 0, j, 1, res);
dfs(matrix, touchdown, m  1, j, 2, res);
}
return res;
}
private void dfs(int[][] matrix, int[][] touchdown, int i, int j, int toState, List<int[]> res) {
if (i < 0  j < 0  i >= m  j >= n) return;
if (!updateState(touchdown, i, j, toState, res)) {
return;
}
if (i + 1 < m && matrix[i][j] <= matrix[i + 1][j]) {
dfs(matrix, touchdown, i + 1, j, toState, res);
}
if (j + 1 < n && matrix[i][j] <= matrix[i][j + 1]) {
dfs(matrix, touchdown, i, j + 1, toState, res);
}
if (i  1 >= 0 && matrix[i][j] <= matrix[i  1][j]) {
dfs(matrix, touchdown, i  1, j, toState, res);
}
if (j  1 >= 0 && matrix[i][j] <= matrix[i][j  1]) {
dfs(matrix, touchdown, i, j  1, toState, res);
}
}
private boolean updateState(int[][] touchdown, int i, int j, int toState, List<int[]> res) {
int currState = touchdown[i][j];
if (currState == 3  currState == toState) return false;
if (currState == 0) {
touchdown[i][j] = toState;
} else {
touchdown[i][j] = 3;
res.add(new int[]{i, j});
}
return true;
}
}