# Java DFS and BFS solution

• 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;
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';
}
}
}``````

• any idea whats the upper bound time complexity of each?

• right I am wondering what is the DFS time complexity

• 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)

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

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

• @Vickyer Hi thanks for pointing out! Can you explain more on the space complexity of recursive DFS solution? I fond it hard to think of the space complexity when we're not explicitly using stack/queue.

Thank you so much!

• Why do we need code variable here?

Is it right to offer grid[i][j] and use x, y (passed from numIslands) , then check x+-1 and y+-1??

• @ke8511369 You have two for loops, and in the nested for loop, we do flood fill. Then the complexity should be O(m * n * number of flood fill visited nodes)
In the flood fill, we only visit node with '1', so the time complexity should be O(m * n * number of '1' in the grid)

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