# Number of Islands BFS solution, beats 92%

• Strategy : Breadth First Search
Logic : We iterate over the "grid" (input array). Every time we find a '1' (island), we change it's value in the grid to '-' and check it's adjacent (left,right,top,bottom) values in the array. If it's adjacent values are also '1' it means that it is a part of the same island. So we change it's value to '-' and again check for it's adjacent values. If the adjacent values are '0' or '-' (we have visited it already) then we do nothing. We use this BFS approach till all the adjacent values or '-' or '0' or we reach the grid boundaries. Thus we get one island. When we iterate over the grid array we will get all islands.

Time Complexity : O(n^2)

Code:

``````class Solution {
int row,col;
public int numIslands(char[][] grid) {

int count = 0;

row = grid.length;
if(row==0)
return 0;
col = grid[0].length;
if(col==0)
return 0;

for(int i=0; i<row; i++){
for(int j=0; j<col;j++){

if(grid[i][j]=='1'){
count++;
island(grid,i,j);
}
}
}

return count;
}

void island(char[][] grid, int i, int j){

if(i<0 || j<0 || i>=row || j>=col){
return;
}
else{

if(grid[i][j]=='1'){
grid[i][j]='-';
island(grid,i,j-1);
island(grid,i,j+1);
island(grid,i-1,j);
island(grid,i+1,j);
}
}
}
}
``````

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