Number of Islands BFS solution, beats 92%


  • 0
    A

    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);               
                }
            }       
        }   
    }
    

Log in to reply
 

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