Finding the number of islands using DFS
The idea is to modify the given matrix, and perform DFS to find the total number of islands
Follow the steps below to solve the problem:
- Initialize count = 0, to store the answer.
- Traverse a loop from 0 till ROW
- Traverse a nested loop from 0 to COL
- If the value of the current cell in the given matrix is 1
- Increment count by 1
- Call DFS function
- If the cell exceeds the boundary or the value at the current cell is 0
- Return.
- Update the value at the current cell as 0.
- Call DFS on the neighbor recursively
- If the cell exceeds the boundary or the value at the current cell is 0
- If the value of the current cell in the given matrix is 1
- Traverse a nested loop from 0 to COL
- Return count as the final answer.
Below is the code implementation of the above approach:
// C++Program to count islands in boolean 2D matrix
#include <bits/stdc++.h>
using namespace std;
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(vector<vector<int> >& M, int i, int j, int ROW,
int COL)
{
// Base condition
// if i less than 0 or j less than 0 or i greater than
// ROW-1 or j greater than COL- or if M[i][j] != 1 then
// we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1)
|| M[i][j] != 1) {
return;
}
if (M[i][j] == 1) {
M[i][j] = 0;
DFS(M, i + 1, j, ROW, COL); // right side traversal
DFS(M, i - 1, j, ROW, COL); // left side traversal
DFS(M, i, j + 1, ROW, COL); // upward side traversal
DFS(M, i, j - 1, ROW,
COL); // downward side traversal
DFS(M, i + 1, j + 1, ROW,
COL); // upward-right side traversal
DFS(M, i - 1, j - 1, ROW,
COL); // downward-left side traversal
DFS(M, i + 1, j - 1, ROW,
COL); // downward-right side traversal
DFS(M, i - 1, j + 1, ROW,
COL); // upward-left side traversal
}
}
int countIslands(vector<vector<int> >& M)
{
int ROW = M.size();
int COL = M[0].size();
int count = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (M[i][j] == 1) {
count++;
DFS(M, i, j, ROW, COL); // traversal starts
// from current cell
}
}
}
return count;
}
// Driver Code
int main()
{
vector<vector<int> > M = { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
cout << "Number of islands is: " << countIslands(M);
return 0;
}
// This code is contributed by ajaymakvana.
// Code improved by Animesh Singh
// Java Program to count islands in boolean 2D matrix
import java.util.*;
public class Main {
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
static void DFS(int[][] M, int i, int j, int ROW,
int COL)
{
// Base condition
// if i less than 0 or j less than 0 or i greater
// than ROW-1 or j greater than COL- or if M[i][j]
// != 1 then we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1)
|| M[i][j] != 1) {
return;
}
if (M[i][j] == 1) {
M[i][j] = 0;
DFS(M, i + 1, j, ROW,
COL); // right side traversal
DFS(M, i - 1, j, ROW,
COL); // left side traversal
DFS(M, i, j + 1, ROW,
COL); // upward side traversal
DFS(M, i, j - 1, ROW,
COL); // downward side traversal
DFS(M, i + 1, j + 1, ROW,
COL); // upward-right side traversal
DFS(M, i - 1, j - 1, ROW,
COL); // downward-left side traversal
DFS(M, i + 1, j - 1, ROW,
COL); // downward-right side traversal
DFS(M, i - 1, j + 1, ROW,
COL); // upward-left side traversal
}
}
static int countIslands(int[][] M)
{
int ROW = M.length;
int COL = M[0].length;
int count = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (M[i][j] == 1) {
count++;
DFS(M, i, j, ROW,
COL); // traversal starts from
// current cell
}
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int[][] M = { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
System.out.print("Number of islands is: "
+ countIslands(M));
}
}
// This code is contributed by suresh07.
// Code improved by Animesh Singh
# Program to count islands in boolean 2D matrix
class Graph:
def __init__(self, row, col, graph):
self.ROW = row
self.COL = col
self.graph = graph
# A utility function to do DFS for a 2D
# boolean matrix. It only considers
# the 8 neighbours as adjacent vertices
def DFS(self, i, j):
if (i < 0 or i >= len(self.graph) or
j < 0 or j >= len(self.graph[0]) or
self.graph[i][j] != 1):
return
# mark it as visited
self.graph[i][j] = -1
# Recur for 8 neighbours
self.DFS(i - 1, j - 1)
self.DFS(i - 1, j)
self.DFS(i - 1, j + 1)
self.DFS(i, j - 1)
self.DFS(i, j + 1)
self.DFS(i + 1, j - 1)
self.DFS(i + 1, j)
self.DFS(i + 1, j + 1)
# The main function that returns
# count of islands in a given boolean
# 2D matrix
def countIslands(self):
# Initialize count as 0 and traverse
# through the all cells of
# given matrix
count = 0
for i in range(self.ROW):
for j in range(self.COL):
# If a cell with value 1 is not visited yet,
# then new island found
if self.graph[i][j] == 1:
# Visit all cells in this island
# and increment island count
self.DFS(i, j)
count += 1
return count
graph = [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
row = len(graph)
col = len(graph[0])
g = Graph(row, col, graph)
print("Number of islands is:", g.countIslands())
# This code is contributed by Shivam Shrey
// C# Program to count islands in boolean 2D matrix
using System;
using System.Collections.Generic;
class GFG {
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
static void DFS(int[, ] M, int i, int j, int ROW,
int COL)
{
// Base condition
// if i less than 0 or j less than 0 or i greater
// than ROW-1 or j greater than COL- or if M[i][j]
// != 1 then we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1)
|| M[i, j] != 1) {
return;
}
if (M[i, j] == 1) {
M[i, j] = 0;
DFS(M, i + 1, j, ROW,
COL); // right side traversal
DFS(M, i - 1, j, ROW,
COL); // left side traversal
DFS(M, i, j + 1, ROW,
COL); // upward side traversal
DFS(M, i, j - 1, ROW,
COL); // downward side traversal
DFS(M, i + 1, j + 1, ROW,
COL); // upward-right side traversal
DFS(M, i - 1, j - 1, ROW,
COL); // downward-left side traversal
DFS(M, i + 1, j - 1, ROW,
COL); // downward-right side traversal
DFS(M, i - 1, j + 1, ROW,
COL); // upward-left side traversal
}
}
static int countIslands(int[, ] M)
{
int ROW = M.GetLength(0);
int COL = M.GetLength(1);
int count = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (M[i, j] == 1) {
count++;
DFS(M, i, j, ROW,
COL); // traversal starts from
// current cell
}
}
}
return count;
}
// Driver code
static void Main()
{
int[, ] M = { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
Console.Write("Number of islands is: "
+ countIslands(M));
}
}
// This code is contributed by decode2207.
// Code improved by Animesh Singh
// Javascript Program to count islands in boolean 2D matrix
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
function DFS(M, i, j, ROW, COL)
{
// Base condition
// if i less than 0 or j less than 0 or i greater than ROW-1 or
//j greater than COL- or if M[i][j] != 1 then we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1) || M[i][j] != 1)
{
return;
}
if (M[i][j] == 1)
{
M[i][j] = 0;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
function countIslands(M)
{
let ROW = M.length;
let COL = M[0].length;
let count = 0;
for (let i = 0; i < ROW; i++)
{
for (let j = 0; j < COL; j++)
{
if (M[i][j] == 1)
{
count++;
DFS(M, i, j, ROW, COL); //traversal starts from current cell
}
}
}
return count;
}
let M = [[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]];
console.log("Number of islands is: " + countIslands(M));
// This code is contributed by divyesh072019.
// Code improved by Animesh Singh
Output
Number of islands is: 5
Time complexity: O(ROW x COL), where ROW is the number of rows and COL is the number of columns in the given matrix.
Auxiliary Space: O(ROW * COL), as to do DFS we need extra auxiliary stack space.
Using Extra O(n*m) Space:
Approach:
In this approach we are traversing over matrix and if the current element is equal to one and not visited already than we mark all connect(mark visit) element/point as visited and increment count (cnt) by one.
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
//valid row and column checker.
bool check(int i,int j){
return i>=0&&j>=0&&i<n&&j<m;
}
void mark_component(vector<vector<int>>&v,vector<vector<bool>>&vis,int i,int j){
if(!check(i,j))return;
vis[i][j]=1;
//marking(connecting all possible part of single island.
if (v[i][j] == 1) {
v[i][j] = 0;
mark_component(v,vis,i+1,j);
mark_component(v,vis,i-1,j);
mark_component(v,vis,i,j+1);
mark_component(v,vis,i,j-1);
mark_component(v,vis,i+1,j+1);
mark_component(v,vis,i-1,j-1);
mark_component(v,vis,i+1,j-1);
mark_component(v,vis,i-1,j+1);
}
}
int main() {
vector<vector<int>>v{{ 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 }};
n=v.size();
m=v[0].size();
int cnt=0;
//visit vector.
vector<vector<bool>>vis(n,vector<bool>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!vis[i][j]&&v[i][j]==1){
++cnt;
mark_component(v,vis,i,j);
}
}
}
cout<<"The number of islands in the matrix are :"<<endl;
cout<<cnt<<endl;
//code by Sanket Gode
return 0;
}
import java.io.*;
import java.util.*;
class Main {
static int n, m;
// valid row and column checker
static boolean check(int i, int j)
{
return i >= 0 && j >= 0 && i < n && j < m;
}
static void mark_component(int[][] v, boolean[][] vis,
int i, int j)
{
if (!check(i, j))
return;
vis[i][j] = true;
// marking (connecting all possible parts of single
// island)
if (v[i][j] == 1) {
v[i][j] = 0;
mark_component(v, vis, i + 1, j);
mark_component(v, vis, i - 1, j);
mark_component(v, vis, i, j + 1);
mark_component(v, vis, i, j - 1);
mark_component(v, vis, i + 1, j + 1);
mark_component(v, vis, i - 1, j - 1);
mark_component(v, vis, i + 1, j - 1);
mark_component(v, vis, i - 1, j + 1);
}
}
public static void main(String[] args)
{
int[][] v = { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
n = v.length;
m = v[0].length;
int cnt = 0;
// visit vector
boolean[][] vis = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j] && v[i][j] == 1) {
++cnt;
mark_component(v, vis, i, j);
}
}
}
System.out.println(
"The number of islands in the matrix are: ");
System.out.println(cnt);
}
}
def check(i, j, n, m):
return i >= 0 and j >= 0 and i < n and j < m
def mark_component(v, vis, i, j, n, m):
if not check(i, j, n, m):
return
vis[i][j] = True
if v[i][j] == 1:
v[i][j] = 0
#marking(connecting all possible part of single island.
mark_component(v, vis, i + 1, j, n, m)
mark_component(v, vis, i - 1, j, n, m)
mark_component(v, vis, i, j + 1, n, m)
mark_component(v, vis, i, j - 1, n, m)
mark_component(v, vis, i + 1, j + 1, n, m)
mark_component(v, vis, i - 1, j - 1, n, m)
mark_component(v, vis, i + 1, j - 1, n, m)
mark_component(v, vis, i - 1, j + 1, n, m)
v = [[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]]
n = len(v)
m = len(v[0])
cnt = 0
vis = [[False for j in range(m)] for i in range(n)]
for i in range(n):
for j in range(m):
if not vis[i][j] and v[i][j] == 1:
cnt += 1
mark_component(v, vis, i, j, n, m)
print("The number of islands in the matrix are:")
print(cnt)
# This code is contributed by Shivam Tiwari
using System;
using System.Collections.Generic;
class GFG {
// valid row and column checker
public static bool check(int i, int j, int n, int m)
{
return i >= 0 && j >= 0 && i < n && j < m;
}
public static void mark_component(List<List<int> > v,
List<List<bool> > vis,
int i, int j)
{
int n = v.Count;
int m = v[0].Count;
if (!check(i, j, n, m))
return;
vis[i][j] = true;
// marking (connecting all possible parts of single
// island)
if (v[i][j] == 1) {
v[i][j] = 0;
mark_component(v, vis, i + 1, j);
mark_component(v, vis, i - 1, j);
mark_component(v, vis, i, j + 1);
mark_component(v, vis, i, j - 1);
mark_component(v, vis, i + 1, j + 1);
mark_component(v, vis, i - 1, j - 1);
mark_component(v, vis, i + 1, j - 1);
mark_component(v, vis, i - 1, j + 1);
}
}
public static void Main()
{
List<List<int> > v = new List<List<int> >{
new List<int>{ 1, 1, 0, 0, 0 },
new List<int>{ 0, 1, 0, 0, 1 },
new List<int>{ 1, 0, 0, 1, 1 },
new List<int>{ 0, 0, 0, 0, 0 },
new List<int>{ 1, 0, 1, 0, 1 }
};
int n = v.Count;
int m = v[0].Count;
int cnt = 0;
// visit vector
List<List<bool> > vis = new List<List<bool> >();
for (int i = 0; i < n; i++) {
vis.Add(new List<bool>());
for (int j = 0; j < m; j++) {
vis[i].Add(false);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j] && v[i][j] == 1) {
cnt++;
mark_component(v, vis, i, j);
}
}
}
Console.WriteLine(
"The number of islands in the matrix are :");
Console.WriteLine(cnt);
}
}
// JavaScript program to count the number of islands in a given binary matrix
// valid row and column checker
function check(i, j, n, m) {
return i >= 0 && j >= 0 && i < n && j < m;
}
// marking (connecting all possible parts of single island)
function mark_component(v, vis, i, j, n, m) {
if (!check(i, j, n, m))
return;
vis[i][j] = true;
if (v[i][j] == 1) {
v[i][j] = 0;
mark_component(v, vis, i + 1, j, n, m);
mark_component(v, vis, i - 1, j, n, m);
mark_component(v, vis, i, j + 1, n, m);
mark_component(v, vis, i, j - 1, n, m);
mark_component(v, vis, i + 1, j + 1, n, m);
mark_component(v, vis, i - 1, j - 1, n, m);
mark_component(v, vis, i + 1, j - 1, n, m);
mark_component(v, vis, i - 1, j + 1, n, m);
}
}
function countIslands(v) {
let n = v.length;
let m = v[0].length;
let cnt = 0;
// visit vector
let vis = new Array(n).fill().map(() => new Array(m).fill(false));
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (!vis[i][j] && v[i][j] == 1) {
++cnt;
mark_component(v, vis, i, j, n, m);
}
}
}
console.log("The number of islands in the matrix are: ");
console.log(cnt);
}
// Sample matrix input
let v = [[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]];
countIslands(v);
// This code is contributed by Shivam Tiwari
Output
The number of islands in the matrix are : 5
Time complexity: O(n*m).
Auxiliary Space: O(n*m).
Find the number of islands using DFS
Given a binary 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 4 islands.
Example:
Input: mat[][] = {{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 0}}
Output: 4
This is a variation of the standard problem: “Counting the number of connected components in an undirected graph”.
Before we go to the problem, let us understand what is a connected component. A connected component of an undirected graph is a subgraph in which every two vertices are connected to each other by a path(s), and which is connected to no other vertices outside the subgraph.
For example, the graph shown below has three connected components.
A graph where all vertices are connected with each other has exactly one connected component, consisting of the whole graph. Such a graph with only one connected component is called a Strongly Connected Graph.
This problem can be easily solved by applying DFS() on each component. In each DFS() call, a component or a sub-graph is visited. We will call DFS on the next un-visited component. The number of calls to DFS() gives the number of connected components. BFS can also be used.
What is an island?
A group of connected 1s forms an island. For example, the below matrix contains 4 islands