Java DFS and BFS solution


  • 25
    Z

    Using Flood Fill algorithm:

    DFS:

    public int numIslands(char[][] grid) {
        int count=0;
        for(int i=0;i<grid.length;i++)
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    dfsFill(grid,i,j);
                    count++;
                }
            }
        return count;
    }
    private void dfsFill(char[][] grid,int i, int j){
        if(i>=0 && j>=0 && i<grid.length && j<grid[0].length&&grid[i][j]=='1'){
            grid[i][j]='0';
            dfsFill(grid, i + 1, j);
            dfsFill(grid, i - 1, j);
            dfsFill(grid, i, j + 1);
            dfsFill(grid, i, j - 1);
        }
    }
    

    BFS:

    public int numIslands(char[][] grid) {
        int count=0;
        for(int i=0;i<grid.length;i++)
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    bfsFill(grid,i,j);
                    count++;
                }
            }
        return count;
    }
    private void bfsFill(char[][] grid,int x, int y){
        grid[x][y]='0';
        int n = grid.length;
        int m = grid[0].length;
        LinkedList<Integer> queue = new LinkedList<Integer>();  
        int code = x*m+y;  
        queue.offer(code);  
        while(!queue.isEmpty())  
        {  
            code = queue.poll();  
            int i = code/m;  
            int j = code%m;  
            if(i>0 && grid[i-1][j]=='1')    //search upward and mark adjacent '1's as '0'.
            {  
                queue.offer((i-1)*m+j);  
                grid[i-1][j]='0';  
            }  
            if(i<n-1 && grid[i+1][j]=='1')  //down
            {  
                queue.offer((i+1)*m+j);  
                grid[i+1][j]='0';  
            }  
            if(j>0 && grid[i][j-1]=='1')  //left
            {  
                queue.offer(i*m+j-1);  
                grid[i][j-1]='0';  
            }  
            if(j<m-1 && grid[i][j+1]=='1')  //right
            {  
                queue.offer(i*m+j+1);  
                grid[i][j+1]='0';  
            }
        } 
    }

  • 0
    M

    any idea whats the upper bound time complexity of each?


  • 0
    H

    right I am wondering what is the DFS time complexity


  • 4
    K

    the time complexity is the same for both ways.
    let grid row length be m, grid col length as n.

    cuz bascially it just iterate the grid, cell by cell, one each cell, DFS or BFS at most will visit m*n cells. but for the cells it visited, we marks it so the next visit in the for loop in main function will be terminated immediately.

    So basically they both visit the whole grid twice. So it is O(m*n)


  • 0
    A

    @ke8511369 I agree with you, how about space complexity? any ideas?


  • 2
    V

    @AllanFly120
    I think also O(mn) space for both recursive/stack DFS and Queue BFS.


Log in to reply
 

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