Java Solution DFS


  • 0
    Z
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> list = new ArrayList<>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return list;
        }
        int length = matrix.length;
        int width = matrix[0].length;
        
        boolean[][] pacific = new boolean[length][width];
        boolean[][] atlantic = new boolean[length][width];
        
        // first row
        for(int j = 0; j < width; j++){
            dfs(matrix, 0, j, Integer.MIN_VALUE, pacific);
        }
        // first column
        for(int i = 0; i < length; i++){
            dfs(matrix, i, 0, Integer.MIN_VALUE, pacific);
        }
        // last row
        for(int j = 0; j < width; j++){
            dfs(matrix, length - 1, j, Integer.MIN_VALUE, atlantic);
        }
        // last column
        for(int i = 0; i < length; i++){
            dfs(matrix, i, width - 1, Integer.MIN_VALUE, atlantic);
        }
        
        for(int i = 0; i < length; i++){
            for(int j = 0; j < width; j++){
                if(pacific[i][j] && atlantic[i][j]){
                    list.add(new int[]{i, j});
                }
            }
        }
        return list;
    }
    
    private void dfs(int[][] matrix, int i, int j, int pre, boolean[][] visited){
        if(i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length){
            return;
        }
        if(visited[i][j]){
            return;
        }
        if(pre > matrix[i][j]){
            return;
        }
        visited[i][j] = true;
        dfs(matrix, i + 1, j, matrix[i][j], visited);
        dfs(matrix, i - 1, j, matrix[i][j], visited);
        dfs(matrix, i, j + 1, matrix[i][j], visited);
        dfs(matrix, i, j - 1, matrix[i][j], visited);
    }

Log in to reply
 

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