• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Number of Islands BFS/DFS

April 5, 2018 by Dhaval Dave

Problem Statement:

Given a 2d grid containing either values either 0 or 1 where 1 represents land and 0 represents water. You have to calculate the number of total islands in the given grid. An island is present when there are more than one 1’s in either up, down, right, left or diagonally.

example depicting what to do

NOTE- You can travel in every direction i.e at most 8 ways to travel from a cell.
 

Solution:

In these type of questions where we have to count the number components and number of elements in each element, we have to use BFS or DFS.

Now first we will calculate the total number of components and then check if the components contain more than one element. If the component contains more than one element then we count it or ignore it.

We will need a visited matrix to keep track of the visited places in the given grid so to avoid over-counting.

Example for counting a component or not.

example for rejecting a component

Code

Implemented in C++ using BFS

#include <bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pp pair<int ,int >
#define ff first
#define ss second
using namespace std;

int m[102][102],vis[102][102];

int dx[]={1,1,0,-1,-1,-1, 0, 1};
int dy[]={0,1,1, 1, 0,-1,-1,-1};						// possible movement directions

int countOfIsland,r,c;

bool check(int i,int j){							// check whether a point is inside a grid or not
  return (0<=i && i<r && 0<=j && j<c);
}

void bfs(int i,int j){			    // Working of bfs:
  countOfIsland++;			        // count the start node of a component
  vis[i][j]=1;			            // make it visited
  queue<pair<int ,int > > q;		// create a queue and
  q.push(mp(i,j));			        // and add the start node to it 
  while(!q.empty()){			    // Now till the queue is not empty, do
    pp u=q.front();			        // store and pop the first entry from the queue
    q.pop();
    for(int i=0;i<8;i++){		    // Now for all its 8 neighbours,
      int x=u.ff+dx[i],y=u.ss+dy[i];	
      if(check(x,y) && !vis[x][y] && m[x][y]==1){	// check whether they are 1 and not visited
        countOfIsland++;			// if they are then increase the count,
        vis[x][y]=1;				// make them visited and
        q.push(mp(x,y));			// add them to queue
      }
    }
  }
}


int main(){  
  cin>>r>>c;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++)
      cin>>m[i][j];
  }
  int numIsland=0;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(!vis[i][j] && m[i][j]==1){
        countOfIsland=0;
        bfs(i,j);
        //cout<<ct<<"\n";
        if(countOfIsland>1)numIsland++;			// count the components with no. of elements greater than 1
      }
    }    
  }

  cout<<numIsland;
  return 0;
}

Implemented in C++ using DFS

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

int m[102][102],vis[102][102];

int dx[]={1,1,0,-1,-1,-1, 0, 1};
int dy[]={0,1,1, 1, 0,-1,-1,-1};			// possible direction movements

int countOfIsland,r,c;

bool check(int i,int j){			// check whether a point is inside a grid or not
  return (0<=i && i<r && 0<=j && j<c);
}

void dfs(int i,int j){				// Working of dfs :
  countOfIsland++;			       // update the count of newly discovered 1
  vis[i][j]=1;			          // make it visited
  for(int k=0;k<8;k++){			   // Now for all its neighbouring 8 cells,
    int x=i+dx[k],y=j+dy[k];							
    if(check(x,y) && !vis[x][y] && m[x][y]==1){		// check whether they are 1 and not visited till now
      //cout<<x<<" "<<y<<endl;
      dfs(x,y);			            // if thats the case then run dfs on them
    }
  }
}

int main(){  
  cin>>r>>c;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++)
      cin>>m[i][j];
  }
  int numIsland=0;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(!vis[i][j] && m[i][j]==1){
        countOfIsland=0;
        //cout<<i<<" "<<j<<"\n";
        dfs(i,j);
        //cout<<ct<<"\n";
        if(countOfIsland>1)numIsland++;					// count the components with elements greater than 1
      }
    }    
  }

  cout<<numIsland;
  return 0;
}

Complexity

Both time and space complexities are O(|no. of rows|*|no. of columns|).

Number of Islands Article is Published by Arnab Ghosh.
If you want to be a content writer with Gohired.in, please write at career@gohired.in or at admin@gohired.in.

Similar Articles

Filed Under: Adobe Interview Questions, Algorithm, Amazon Interview Question, Data Structure, Graph Tagged With: 2d matrix, BFS, DFS

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

strtok()

Print all nodes that are at distance k from a leaf node

Check if an array has duplicate numbers in O(n) time and O(1) space

Python String and numbers

Code Chef PRGIFT Solution

Count Possible Decodings of a given Digit Sequence

LeetCode : Word Search

Maximum difference between two elements s.t larger element appears after the smaller number

Find position of the only set bit

BFS (Breath First Search)

Doubly linked list

Find Pythagorean Triplets in an array in O(N)

Find two non repeating elements in an array of repeating elements

Find if a binary tree is height balanced ?

Reversal of LinkedList

Common Ancestor in a Binary Tree or Binary Search Tree

Practo Hiring Experience

Trie Dictionary

Sequence Finder Dynamic Programming

Length of the longest substring without repeating characters

Walmart Labs Interview Experience

Generate next palindrome number

Hackerearth : Counting Subarrays

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Test Cases for Round Function

Print Power Set of a Set

Linked List V/S Binary Search Tree

Given Set of words or A String find whether chain is possible from these words or not

Introduction To Number Theory ( Part 1 )

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Copyright © 2025 · Genesis Framework · WordPress · Log in