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


  • 1
    K

    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^2cells 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;
                res.add(new int[]{i, j});
            }
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.