Data Structures & Algorithms in Java – Graphs – Number of Islands

Problem:

Given a m * n grid representing a map with the value 1 representing land and the value 0 representing water,

find out the number of islands in the grid.

That is find out the piece of area containing ‘1’s surrounded on all sides by ‘0’s or the grid boundaries (Assume the entire grid is surrounded by water)

For example,

For the below grid:

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

The output is 1,

Since you can combine all the 1’s adjacent to each other (in either of the four directions and form a single island)

For the below input:

 [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

The output is 3 because if you club together all continuous 1s you get three groups.

Try out the solution here:

https://leetcode.com/problems/number-of-islands/

Advertisements

Solution:

Hint:

Use Depth First Search or Breadth First Search

Explanation:

Imagine the grid as a graph.

And each cell in the grid represents a node in the graph.

There is a connection from one node to another another if their values are 1.

With this model in mind,

You can do a depth first search or breadth first search starting from the first “1” you encounter.

The DFS or BFS search will go deep or wide into the island passing through all the 1s. Mark these 1s as 0 as you visit them so that they are not visited again.

Once one round of DFS or BFS is finished (in all four directions), you get one island.

Then you again search for the next ‘1’ in the grid and do BFS or DFS again.

Depth First Search:

Here is the simple snippet of code that does DFS:

        
        for(int i=0;i<noRows;i++){
            
            
            for(int j=0;j<noCols;j++){
                
                
                if(grid[i][j] =='1'){
                    
                    noOfIslands++;
                    
                    
                    dfs(i,j,grid);
                }
            }
        }

You just increment the number of islands when you encounter a 1 in the grid.

The DFS code will make sure that all continuous 1s starting from this one will be marked as zero.

Here is the DFS code invoked in the above snippet:

 public void dfs(int row,int col,char[][] grid){
        
        
        
        if(row < 0 || row >= noRows || col < 0 || col >= noCols || grid[row][col] == '0'){
            
            return;
        }
        
        grid[row][col] = '0';
        
        dfs(row+1,col,grid);
        dfs(row-1,col,grid);
        
        dfs(row,col+1,grid);
        dfs(row,col-1,grid);
        
        
    }

You just check for boundary conditions and the value of the cell to be “1” to do the DFS.

You mark the visited cells as ‘0’ so that they are not picked again.

Here is the entire code:

class Solution {
    
    
    int noRows;
    
    int noCols;
    
    public int numIslands(char[][] grid) {
        
        if(grid.length == 0) return 0;
        
         noRows = grid.length;
        
         noCols = grid[0].length;
        
        
        int noOfIslands = 0;
        
        
        for(int i=0;i<noRows;i++){
            
            
            for(int j=0;j<noCols;j++){
                
                
                if(grid[i][j] =='1'){
                    
                    noOfIslands++;
                    
                    
                    dfs(i,j,grid);
                }
            }
        }
        
        return noOfIslands;
        
    }
    
    
    public void dfs(int row,int col,char[][] grid){
        
        
        
        if(row < 0 || row >= noRows || col < 0 || col >= noCols || grid[row][col] == '0'){
            
            return;
        }
        
        grid[row][col] = '0';
        
        dfs(row+1,col,grid);
        dfs(row-1,col,grid);
        
        dfs(row,col+1,grid);
        dfs(row,col-1,grid);
        
        
    }
}

So the algorithm is :

  1. If grid is empty return
  2. For each cell in the grid , check if the value is 1
  3. If so increment the number of islands counter and do DFS in all four directions until all consecutive 1s are searched and marked as 0
  4. Continue the DFS for the next cell with value 1.
  5. Repeat until all cells are traversed.

Time complexity:

Since we iterate through each cell once , time complexity is O(m * n ) where m and n represent the length and breadth of the grid

Space complexity:

In the worst case , a recursive call is made for each cell (If all the values in the grid are 1s). So space complexity is O(m * n)

Advertisements

Breadth First Search:

In Breadth First Search , as usual you use queues instead of recursion.

You maintain a queue with the row and column values of cells which have the value 1 in all four directions. You then pop them one by one and repeat the above step (Pushing all neighbors with value 1). Until you encounter a cell with value 0 and you are within the boundary of the grid you keep adding the cell to the queue.

Here is the BFS code:

class Solution {
    
    
    
    
    
    
    public int numIslands(char[][] grid) {
        
        if(grid.length == 0 || grid[0].length ==0) return 0;
        
        int noRows = grid.length;
        
        int noCols = grid[0].length;
        
        
        int noOfIslands = 0;
        
        
        for(int i=0;i<noRows;i++){
            
            
            for(int j=0;j<noCols;j++){
                
                
                if(grid[i][j] =='1'){
                    
                                       
                    noOfIslands++;
                    grid[i][j] = '0';
                    
                    Queue<int[]> q = new LinkedList<>();
                    
                    q.add(new int[]{i,j});
                    
                    
                    while(!q.isEmpty()){
                        
                        
                        int[] node =   q.remove();
                     
                        int row = node[0];
                        int col = node[1];
                        
                        
                        
                        
                        if(row-1 >= 0 && grid[row-1][col] =='1'){
                            
                            
                            q.add( new int[]{row-1,col});
                            
                            
                            grid[row-1][col] ='0';
                        }
                        
                        if(row+1 < noRows &&  grid[row+1][col] == '1'){
                            
                            
                               q.add( new int[]{row+1,col});
                            grid[row+1][col] ='0';
                            
                        }
                        
                        if(col -1 >=0 && grid[row][col-1] == '1'){
                            
                            
                               q.add(new int[]{row,col-1});
                            grid[row][col-1] ='0';
                            
                        }
                        
                        if(col +1 < noCols && grid[row][col+1] =='1'){
                            
                               q.add(new int[]{row,col+1});
                            grid[row][col+1] ='0';
                            
                        }
                        
                    }
                    
                    
                }
            }
        }
        
        return noOfIslands;
        
    }
}

As you see ,

When you first enter a cell with value 1 , you add that to a queue

You then look for neighbors in all four directions with value 1 (and within the grid boundary).

You add them to the queue as well.

While adding to the queue you always mark the value of the cell as zero so that they are not picked again.

Once the neighbors are added you pop the top element in the queue and continue searching for neighbors with value 1 and adding them to the queue.

Time complexity:

You will be iterating through all the cells in the grid once so the time complexity is O(m * n)

Space complexity:

We use an extra queue to do BFS . The size of this queue will always be the minimum of the length and the breadth of the grid.

This can be visualized by the below diagram.

The above is a 4 * 5 grid with all the values as 1 (worst case).

The above traversals show the size of the queue at different points of time.

First you push first element.

Queue size is 1

Then you pop the first element and add its two neighbors .

Queue size is 2.

Then you pop one of these elements and add its neighbors which are not visited yet. (2 elements)

You pop the other element and add its neighbors which are not visited yet (1 element)

Queue size is 3.

It goes on like this in the diagonal direction and the maximum size is 4 as shown in the above diagram.

So space complexity is O(min (m , n))

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s