Reverse flow technique: Clean Java solution using DFS and state machine

• Simple idea:

``````        // 0 not visited
// 1 pacific
// 2 atlantic
// 3 both
``````
1. DFS from first row and first column and mark all the reachable nodes (reverse comparison) as `1`.
If cell is marked as `1` or `3` already, break DFS
If cell is marked as `2` already, mark it `3`

2. DFS from last row and last column and mark all the reachable nodes (reverse comparison) as `2`.
If cell is marked as `2` or `3` already, break DFS
If cell is marked as `1` already, mark it `3`

• Space complexity: `O(n)`
• Time complexity: `O(n^3)`
I guess we can argue that it is `O(n^2)` since we don't visit all the `n^2`cells for the `4n` 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;