Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Find Number Of Islands

Moderate
0/80
Average time to solve is 34m
profile
Contributed by
120 upvotes
Asked in companies
AppleZomatoAtlassian

Problem statement

You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line of input contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.

The second line onwards, the next 'N' lines or rows represent the ith row values.

Each of the i-th row constitutes 'M' column values separated by a single space.
Output Format :
The only line of output prints the number of islands present in the 2-dimensional array.
Note :
You are not required to print anything explicitly, it has already been taken care of. Implement the function and return the desired output.
Constraints :
1 <= N <= 10^3 
1 <= M <= 10^3
0 <= ARR[i][j] <= 1

Time limit: 1sec
Sample Input 1 :
4 5
0 1 1 0 0
1 0 0 1 0
0 0 1 0 0
1 0 0 0 1
Sample Output 1 :
3
Explanation For Sample Input 1 :
The first island of connected 1s is signified by: {0, 1}, {0, 2}, {1, 0}, {1, 3}, {2, 2}.

The second island being: {3, 0}.

The third island being: {3, 4}.
Sample Input 2 :
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
Sample Output 2 :
1
Hint

Think of how we can apply a BFS/DFS like approach to traverse the matrix. Also, think about an efficient way to check all the 8 directions.

Approaches (1)
Flood Fill Algorithm

We can use the flood fill algorithm to check for all connected 1s.

 

  • We create two arrays, dx, and dy, in which we store the unit vectors for all eight directions. Thus, when we are at a given cell, we can easily check for all its adjacent cells by simply looping over the two arrays, adding their values to the current position, and checking for this new position recursively.
  • We will also create a 2D boolean array of the same size as the input array that will keep track of whether a cell has been visited. Initialize an ans variable as 0.
  • Iterate through the input array. For every cell that is equal to 1 and not visited, first increase ans by 1 and use the flood fill algorithm to mark that cell and every other connected cell that is equal to 1 as visited so we don't count them again
  • Return the ans variable
Time Complexity

O(N * M), where N and M are the dimensions of the array.

 

Traversing each cell of the 2D array once requires O(N * M) time.

Space Complexity

O(N * M), where N and M are the dimensions of the array.

 

We have to maintain a boolean 2D array, which keeps track of whether a cell has been visited before or not.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Find Number Of Islands
All tags
Sort by
Search icon

Interview problems

using diagonal element

void dfs(int x,int y,int **arr,vector<vector<int>>&v,int n,int m){

     v[x][y]=1;

     int drow[]={-1,-1,0,1,1,1,0,-1};

     int dcol[]={0,1,1,1,0,-1,-1,-1};

     for(int i=0;i<8;i++){

        int r = x+drow[i];

        int c = y+dcol[i];

        if(r>=0&&r<n&&c>=0&&c<m&&v[r][c]==0 && arr[r][c]==1){

           dfs(r,c,arr,v,n,m);

        }

     }

}

int getTotalIslands(int** arr, int n, int m)

{

   

   int ct=0;

   vector<vector<int>>v(n,vector<int>(m,0));

  for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            if (arr[i][j] == 1 && v[i][j] == 0) {

                dfs(i, j, arr, v, n, m);

                ct++;

            }

        }

    }

    return ct;

}

 

100 views
0 replies
0 upvotes

Interview problems

BFS Solution

#include<bits/stdc++.h>

void bfs(int row ,int col , vector<vector<int>> &vis , int **arr ,int n , int m){
   vis[row][col] = 1;
   queue<pair<int,int>> q;
   
   q.push({row,col});
   int delrow[4] = {-1,0,1,0};
   int delcol[4] = {0,1,0,-1};

   while(!q.empty()){
      int row = q.front().first;
      int col = q.front().second;
      q.pop();

      for(int i = 0 ; i<4 ; i++){
         for(int j = 0 ; j<4 ; j++){
            int nrow = row + delrow[i];
            int ncol = col + delcol[j];

            if(nrow >= 0 && ncol >= 0 && nrow<n && ncol<m && arr[nrow][ncol] == 1 && vis[nrow][ncol] != 1){
               vis[nrow][ncol] = 1;
               q.push({nrow,ncol});
            }
         }
      }
   }
}

int getTotalIslands(int** arr, int n, int m)
{
   vector<vector<int>> vis(n,vector<int>(m,0));
   int islands = 0;

   for(int i  = 0 ; i<n ; i++){
      for(int j = 0 ; j<m ; j++){
         if(arr[i][j] == 1 && vis[i][j] != 1){
            bfs(i,j,vis,arr,n,m);
            islands++;
         }
      }
   }

   return islands;
}
233 views
0 replies
0 upvotes

Interview problems

DFS Solution

void dfs(int row , int col , vector<vector<int>> &vis , int **arr , int n , int m){
   vis[row][col] = 1;

   int delrow[4] = {-1,0,1,0};
   int delcol[4] = {0,1,0,-1};

   for(int i = 0 ; i<4 ; i++){
      for(int j  = 0 ; j<4 ; j++){
         int nrow = row+delrow[i];
         int ncol = col + delcol[i];

         if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && arr[nrow][col] == 1 && vis[nrow][ncol] == 0){
            dfs(nrow,ncol,vis,arr,n,m);
         }
      }
   }
}

int getTotalIslands(int** arr, int n, int m)
{
   vector<vector<int>> vis(n,vector<int>(m,0));
   int islands = 0;

   for(int i  = 0 ; i<n ; i++){
      for(int j = 0 ; j<m ; j++){
         if(arr[i][j] == 1 && vis[i][j] != 1){
            dfs(i,j,vis,arr,n,m);
            islands++;
         }
      }
   }

   return islands;
}
114 views
0 replies
0 upvotes

Interview problems

Easy java solution using dfs approach

public class Solution 

{

    public static int getTotalIslands(int[][] mat) 

    {

        int m = mat.length;

        int n = mat[0].length;

        int count = 0;

        for(int i = 0; i < m; i++) {

            for(int j = 0; j < n; j++) {

                if(mat[i][j] == 1) {

                    count++;

                    dfs(i, j, m, n, mat);

                }

            }

        }

        return count;

    }

 

    public static void dfs(int i, int j, int m, int n, int[][] mat) {

        if(i < 0 || i >= m || j < 0 || j >= n || mat[i][j] == 0) return;

        if(mat[i][j] == 1) {

            mat[i][j] = 0;

            dfs(i + 1, j, m, n, mat);

            dfs(i - 1, j, m, n, mat);

            dfs(i, j + 1, m, n, mat);

            dfs(i, j - 1, m, n, mat);

            dfs(i + 1, j + 1, m, n, mat);

            dfs(i - 1, j + 1, m, n, mat);

            dfs(i + 1, j - 1, m, n, mat);

            dfs(i - 1, j - 1, m, n, mat);

        }

    }

}

140 views
0 replies
1 upvote

Interview problems

DFS EASY CPP

void dfs(int i,int j,int n,int m,int** grid,vector<vector<int>>&vis){
   if(i>=n or j>=m or i<0 or j<0 or vis[i][j]!=0 or grid[i][j]==0) return;
   vis[i][j]=1;
   dfs(i+1,j,n,m,grid,vis);
   dfs(i-1,j,n,m,grid,vis);
   dfs(i,j+1,n,m,grid,vis);
   dfs(i,j-1,n,m,grid,vis);
   dfs(i+1,j+1,n,m,grid,vis);
   dfs(i-1,j+1,n,m,grid,vis);
   dfs(i+1,j-1,n,m,grid,vis);
   dfs(i-1,j-1,n,m,grid,vis);

}
int getTotalIslands(int** grid, int n, int m){
   int cnt=0;
   vector<vector<int>>vis(n,vector<int>(m,0));
   for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
            if(vis[i][j]==0 and grid[i][j]==1){
               cnt++;
               dfs(i,j,n,m,grid,vis);
            }
      }
   }
   return cnt;
}
130 views
0 replies
2 upvotes

Interview problems

Easy Approach by BFS.....straight forward

#include<queue>

#include<bits/stdc++.h>

#include<unordered_map>

 

void bfs(int row,int col,vector<vector<int>> &visited,int** &arr,int n,int m){

   visited[row][col] = 1;

   queue<pair<int,int>> q;

   q.push(make_pair(row,col));

 

   while(!q.empty()){

      int row = q.front().first;

      int col = q.front().second;

      q.pop(); 

      for(int i = -1;i<=1;i++){

         for(int j = -1;j<=1;j++){

            int nrow = row + i;

            int ncol = col + j;

 

            if(nrow >=0 && nrow<n && ncol>=0 && ncol<m && !visited[nrow][ncol] && arr[nrow][ncol] == 1){

               visited[nrow][ncol] = 1;

               q.push(make_pair(nrow,ncol));

            }

         }

      }

   }

}

 

int getTotalIslands(int** arr, int n, int m)

{

   // Write your code here.

   int count = 0;

   vector<vector<int>> visited(n,vector<int>(m,0));

   for(int i =0;i<n;i++){

      for(int j =0;j<m;j++){

         if(!visited[i][j] && arr[i][j] == 1){

            count++;

            bfs(i,j,visited,arr,n,m);

         }

      }

   }

 

   return count;

}

 

98 views
0 replies
0 upvotes

Interview problems

Easiest c++ Solution.. with explanation

#include<bits/stdc++.h>
void bfs(int row , int col  , vector<vector<int>> &vis , int ** arr , int n , int m)
{
   //creating queue of type pair to store both row and col
   queue<pair<int , int>> q;

   q.push({row ,col});
   //mark row ,col as visited;
   vis[row][col]=1;
   while(!q.empty())
   {
       int row= q.front().first;
       int col =q.front().second;
       q.pop();
       
       //treversing through all 8 sides of row,col 
       for(int delrow=-1;delrow<=1;delrow++)
       {
          for(int delcol=-1;delcol<=1;delcol++)
          {
             int neighbourRow= row+delrow;
             int neighbourCol= col+delcol;
             //check wheher it lies in range or not & should be not visited & neighbor should be 1
             if(neighbourRow >=0 && neighbourRow < n && neighbourCol>=0 && neighbourCol<m &&  arr[neighbourRow][neighbourCol]==1 && !vis[neighbourRow][neighbourCol])
             { 
                //push it to ourq just like bfs traversl
                q.push({neighbourRow , neighbourCol});
                vis[neighbourRow][neighbourCol]=1;
             }

          }
       }

   }
}
int getTotalIslands(int** arr, int n, int m)
{
   // Write your code here.
   //create vis 2d matrix
   vector<vector<int>> vis( n ,vector<int>(m ,0));
   int cnt=0;
   for(int i=0;i<n;i++)
   {
      for(int j=0;j<m;j++)
      {
         if(!vis[i][j] && arr[i][j]==1)
         {
            cnt++;
            bfs( i , j , vis , arr , n, m);
         }
      }
   }
   return cnt;


}
133 views
0 replies
2 upvotes

Interview problems

C++ CLEAN & EASY SOLUTION (USING BFS)

#include <bits/stdc++.h>
void bfs(int row, int col, vector<vector<int>>&vis, int **arr, int n, int m)
{
   vis[row][col] = 1;

   queue<pair<int,int>>q;
   q.push({row,col});
   while(!q.empty())
   {
      int r = q.front().first;
      int c = q.front().second;
      q.pop();
      for(int delrow = -1; delrow <= 1; delrow++)
      {
         for(int delcol = -1; delcol <= 1; delcol++)
         {
            int nrow = r+delrow;
            int ncol = c+delcol;

            if(nrow>=0 && nrow<n && ncol>=0 && ncol<m &&
            vis[nrow][ncol]==0 && arr[nrow][ncol]==1)
            {
               vis[nrow][ncol] = 1;
               q.push({nrow,ncol});
            }
         }
      }
   }
}
int getTotalIslands(int** arr, int n, int m)
{
   vector<vector<int>>vis(n,vector<int>(m,0));
   int count = 0;
   for(int i = 0; i < n; i++)
   {
      for(int j = 0; j < m; j++)
      {
        if (!vis[i][j] && arr[i][j] == 1)
        {
            count++;
            bfs(i, j, vis, arr, n, m);
        }
      }
   }
   return count;
}
85 views
0 replies
0 upvotes

Interview problems

Java easy solution

import java.util.*;

public class Solution 
{
    public static void drawTree(int [][] arr, int i, int j, boolean [][] visited){
        if(i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 0
         || visited[i][j] == true){
             return;
         }
        visited[i][j] = true;
        // horizontal and vertical call
        drawTree(arr,i + 1,j,visited);
        drawTree(arr,i - 1,j,visited);
        drawTree(arr,i ,j + 1,visited);
        drawTree(arr,i,j - 1,visited);
        // diagonal calls
        drawTree(arr,i + 1,j + 1,visited);
        drawTree(arr,i - 1,j - 1,visited);
        drawTree(arr,i - 1,j + 1,visited);
        drawTree(arr,i + 1,j - 1,visited);
    }
    public static int getTotalIslands(int[][] grid) 
	{
        //Your code goes here
        int m = grid[0].length;
        int n = grid.length;
        boolean visited [][] = new boolean[grid.length][grid[0].length];
        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 && visited[i][j] == false){
                    drawTree(grid, i, j, visited);
                    count++;
                }
            }
        }
        return count;
    }
}

java

programming

136 views
0 replies
0 upvotes

Interview problems

Simple DFS in Graph

Approach: Start from [0][0], check if the node is an island,i.e=1, mark it visited, and call DFS to mark all its neighboring nodes as marked 0 or -1.

 

Just take a count of how many times you have to start the DFS call afresh.

 

Time Complexity - O(n*m)

Space Complexity - O(n+m) for stack space

 

Code:

void dfs(int** arr,int i,int j,int n,int m)
{
   arr[i][j]=0;// marked visited

   int dx[]={0,-1,-1,-1,0,1,1,1};
   int dy[]={-1,-1,0,1,1,1,0,-1};

   for(int k=0;k<8;k++)
   {
      int row=i+dx[k],col=j+dy[k];
      if(row>=0 && row<n && col>=0 && col<m && arr[row][col]==1)
      {
         dfs(arr,row,col,n,m);
      }
   }
}
int getTotalIslands(int** arr, int n, int m)
{
   // Write your code here.
   int cnt=0;
   for(int i=0;i<n;i++)
   {
      for(int j=0;j<m;j++)
      {
         if(arr[i][j]==1)
         {
            cnt++;
            dfs(arr,i,j,n,m);
         }
      }
   }

   return cnt;

}
136 views
0 replies
0 upvotes
Full screen
Console