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

  • 0
    Z

    Hi, you code is very nice and readable and we love it very much. However, are you sure the strategy you're using is BFS? I think this is Recursive DFS.


  • 0

    @akshayhonap619 @zhenjieh Hi. We are deprecating this site and it is almost done.
    The new discuss is leetcode.com/discuss. For discuss of each problems, you can see it on the nav tab of the question detail page.
    For example, for this question, the url is https://leetcode.com/problems/number-of-islands/discuss/.


Log in to reply
 

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