Find the number of islands

 Given a grid consisting of '0's(Water) and '1's(Land). Find the number of islands.

Note: An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically or diagonally i,e in all 8 directions.
 

Example 1:

Input:
grid = {{0,1},{1,0},{1,1},{1,0}}
Output:
1
Explanation:
The grid is-
0 1
1 0
1 1
1 0
All lands are connected.

Example 2:

Input:
grid = {{0,1,1,1,0,0,0},{0,0,1,1,0,1,0}}
Output:
2
Expanation:
The grid is-
0 1 1 1 0 0 0
0 0 1 1 0 1 0 
There are two islands one is colored in blue 
and other in orange.

 


method:

finding the no. of connected components in the grid is same as Connected Components in an undirected graph

also check how to find depth first search in grid DFS on a 2D array/2D grid

here we have to use all 8 direction around a cell


c++ implementation: using arrays


#include<bits/stdc++.h>
using namespace std;
int n ;int m;
int vis[1001][1001];
int grid[1001][1001];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};

void dfs(int x,int y)
{
     
    vis[x][y]=1;
for (int i=0;i<8;i++)
{ int u=x+dx[i];int v=y+dy[i];
if(u>=0 && u<n && v>=0 && v<m && vis[u][v]==0 && grid[u][v]==1)
        dfs(u,v);
}
}


int main(){
	int t; // no. of test cases
	cin>>t;
	
	while(t--)
	{
		cin >> n >> m;
		
		
		for(int i = 0; i < n; i++)
                {
			for(int j = 0; j < m; j++)
                        {
				cin >> grid[i][j];
				vis[i][j]=0;
			}
		}
			int c=0; //for counting 
		for(int i = 0; i < n; i++)
               {
			for(int j = 0; j < m; j++)
                        {
				if(vis[i][j]==0 && grid[i][j]==1)
				{
				    dfs(i,j);
				    c++;
				}
			}
		}
	
             cout<<c<<" ";
	}
} 

 

  • Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
  • Space Complexity :O(V). 





c++ implementation: using vectors

#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends
class Solution {
public:
//the main number of island program starts here
int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]={-1,0,1,-1,1,-1,0,1}; void dfs(vector<vector<char>>&A,vector<vector<int>> &vis,int x,int y,int N,int M) { vis[x][y]=1; for (int i=0;i<8;i++) { int u=x+dx[i];int v=y+dy[i]; if(u>=0 && u<N && v>=0 && v<M && vis[u][v]==0 && A[u][v]=='1') dfs(A,vis,u,v,N,M); } } int numIslands(vector<vector<char>>& A){ int count=0; int N=A.size(); int M=A[0].size(); 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 && A[i][j]=='1') {dfs(A,vis,i,j,N,M); count++;}} } return count; } //ends here
};
// { Driver Code Starts. int main(){ int tc; cin >> tc; while(tc--){ int n, m; cin >> n >> m; vector<vector<char>>grid(n, vector<char>(m, '#')); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> grid[i][j]; } } Solution obj; int ans = obj.numIslands(grid); cout << ans <<'\n'; } return 0; } // } Driver Code Ends


  • Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
  • Space Complexity :O(V). 



darkmode