What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Number of Islands (With C++, Java and Python Code)

  • Meter showing medium difficulty level Difficulty Level - Medium
    DFS

 

Finding the total number of islands is one of the most asked interview questions till date. A product-based company like Adobe and Infosys frequently asked this question as a part of their technical interview. As the number of island problems includes the concept and application of data structures and graphs, it helps the interviewer test the candidate's understanding for the same.

Problem: Find the Number of Islands

You are given a matrix “mat” with dimensions m*n, which represents a map of “1’s” as a land of the island and “0’s” as the water around the island. Island is surrounded by the water and connects adjacent lands horizontally and vertically, as shown in the figure below. Find out the total number of islands.

Number of islands example matrix

Before we start coding the problem's solution, let us first understand the problem description and working of the problem to find the solution.

Approach:

Looking at the above problem description, the "Number of island" problem is a variable of the standard problem “Find the number of connected components in an undirected graph.” As you know, a graph is a group of nodes and edges that are used to connect these nodes. Therefore, the connected component of an undirected graph is a subgraph where every two nodes are connected by a path(s). The below image shows the connected components of the graph.

Connected component of graph

The given problem can be solved easily using Depth First Search Algorithm(DFS) on each component. Depth First Search Algorithm is a recursive algorithm that uses backtracking to search all the nodes of the graph by going ahead if the potential node is found, else use the backtracking approach. When DFS is called, a component of the undirect graph is visited. After the complete iteration, we will call DFS again on the next un-visited component. Therefore, the number of calls of DFS gives the total number of connected components of the graph.

Now comparing the connected components of an undirected graph with the "Number of island" problem, the node of the graph will be the “1’s” (land) in the matrix. We will call the depth-first search algorithm on the ‘1's’ of the matrix. Later during the DFS call, every visited cell of the matrix is set as ‘0’ to mark it as a visited node. At last, count the number of total DFS calls, which indicates the total number of islands since each DFS call starts when a new island is identified.

Let's take a look at the example below for a better understanding.

Example

Consider a matrix “mat” of size 3x3 i.e. m=n=3. The “1’s” in the matrix represent the island's land area, and the “0’s” represent the water around the island.

Number of islands example matrix

Now, we will call the DFS algorithm from the first cell, i.e., mat[0][0] of the matrix. The algorithm will traverse all the matrix cells containing “1’s” by using the recursive backtracking method, as shown below in the highlighted area.

Applying DFS algorithm to find first set of island

After each visit of the cell containing “1’s”, we will replace it with “0” to mark the cell as visited and avoid the repetition of the algorithm.

Applying DFS to find second set of island

Later again, we call the DFS algorithm on the other matrix cell containing “1” but not visited previously. The process keeps repeating until all the cells of the matrix are zero.

Repeating the process until all cells becomes zero

To find out the total number of islands as the final output of the problem, we will count the number of DFS calls throughout the problem. Therefore, for the given matrix, the number of islands is 2.

Final output for number of island

Time Complexity

The running time complexity for finding the number of islands for the given matrix is O(m*n), where m and n are rows and columns, respectively.

The space complexity of the problem is O(min(m,n)) as in the worst case where the matrix is filled with lands, and the size of the queue can grow up to min(m,n).

 

It's now time to test your own code in our compiler

Top 10 Problems

Number of Islands Solutions

 

1) C++ Code

 

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

void DepthFirstSearch(vector<vector<int>> &mat, int i, int j, int row, int col)
{
    if (i < 0 || j < 0 || i > (row - 1) || j > (col - 1) || mat[i][j] != 1){        // If index is not in range within range then return
        return;
    }
    if (mat[i][j] == 1){
        mat[i][j] = 0;
        DepthFirstSearch(mat, i + 1, j, row, col);
        DepthFirstSearch(mat, i - 1, j, row, col);
        DepthFirstSearch(mat, i, j + 1, row, col);
        DepthFirstSearch(mat, i, j - 1, row, col);
    }
}

int NumIslands(vector<vector<int>> &mat, int row, int col){
    int count = 0;
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++){
            if (mat[i][j] == 1){
                mat[i][j] = 0;
                count++;
                DepthFirstSearch(mat, i + 1, j, row, col);
                DepthFirstSearch(mat, i - 1, j, row, col);
                DepthFirstSearch(mat, i, j + 1, row, col);
                DepthFirstSearch(mat, i, j - 1, row, col);
            }
        }
    }
    return count;
}

int main(){
    int t;
    cin>>t;                         // t test cases
    while(t--){
        int n,m,x;
        cin>>n>>m;
        vector<vector<int>> mat;
        // Input the mat
        for(int i=0;i<n;i++){
            vector<int> p;
            for(int j=0;j<m;j++){
                cin>>x;
                p.push_back(x);
            }
            mat.push_back(p);
        }
        cout<<NumIslands(mat,n,m)<<endl;
    }
    return 0;
}

 

2) Java Code

 

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int testCases = sc.nextInt(); // Number of test cases
		for(int i=0;i<testCases;i++){
			int m = sc.nextInt(); // Number of rows
			int n = sc.nextInt(); // Number of columns
			int mat[][] = new int[m][n];
			for(int j=0;j<m;j++){
				for(int k=0;k<n;k++){
					mat[j][k] = sc.nextInt();
				}
			}
			int numberOfIslands = 0; // Initializing number of islands with 0
			for(int j=0;j<m;j++){
				for(int k=0;k<n;k++){
					if(mat[j][k] == 1){
						countNumberOfIslands(j, k, mat); // recursive function which counts each island
						numberOfIslands+=1;
					}
				}
			}
			System.out.println(numberOfIslands); // Final result (Total number of islands)
		}
	}
	public static void countNumberOfIslands(int i, int j, int[][] mat){
		if(i == mat.length || j == mat[0].length || i<0 || j<0)
			return; // base case
		if(mat[i][j] == 0)
			return;
		mat[i][j] = 0;
		countNumberOfIslands(i+1,j,mat); // checking in downward direction
		countNumberOfIslands(i,j+1,mat); // checking in right direction
		countNumberOfIslands(i-1,j,mat); // checking in upward direction
		countNumberOfIslands(i,j-1,mat); // checking in left direction
	}
}

 

3) Python Code

 

class Solution :
   def Islands ( self , grid) :
       if not grid : return 0
       def dfs ( i , j , grid ) :
           if i < 0 or j < 0 or i >= row or j >= col or grid [ i ] [ j ] == 0 :
               return
           grid [ i ] [ j ] = 0	# Mark cell as zero to avoid recounting
           dfs ( i + 1 , j , grid )		
           dfs ( i - 1 , j , grid )
           dfs ( i , j + 1 , grid )
           dfs ( i , j - 1 , grid )
           return
       islands = 0
       row = len ( grid )
       col = len ( grid [ 0 ] )
       for i in range ( 0 , row ) :	# Traverse grid
           for j in range ( 0 , col ) :
               if grid [ i ] [ j ] == 1 :
                   dfs ( i , j , grid )
                   islands += 1
       return islands

if __name__ == '__main__':
    mat = [[1, 1, 1], [1, 0, 0], [1, 0, 1 ]]
    print('Number of Islands : ',Solution().Islands(mat))

It's now time to test your own code in our compiler