Skip to main content

Number of Islands

In this page, we will solve the Number of Islands problem using Two different approaches: Breadth First Search (BFS) and Depth First Search (DFS) technique. We will provide the implementation of the solution in C++, Python, Java.

Problem Description​

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Examples​

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Constraints​

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

Solution for Number of Islands Problem​

Intuition and Approach​

This solution employs a Breadth-First Search (BFS) and Depth First Search (DFS) approach to traverse the grid, identifying islands by exploring contiguous land cells Eight Directionally. It marks visited cells to avoid redundant exploration and counts the number of separate island formations encountered.

Approach 1: Breadth First Search (BFS)​

The breadth-first search (BFS) algorithm to traverse through the grid and identify connected components, a count variable to keep track of the number of islands found after that we initializes a 2D vector called vis to mark visited cells in the grid. For each unvisited cell (grid[row][col] == '1' and vis[row][col] == 0), it increments the count and invokes the bfs function to explore the island further. Inside bfs, it marks the current cell as visited and pushes it onto a queue. It then enters a while loop where it queues cells from the queue and explores their neighboring cells. For each neighboring cell that meets the criteria of being within bounds, containing '1', and not visited yet, it marks it as visited and enqueues it for further exploration.The loop continues until the queue is empty, indicating that the entire island has been explored. After exploring all cells in the grid, we returns the count of islands found.

Codes in Different Languages​

Written by @aryan-1309

class Solution {
public:
void bfs(int row, int col,int m, int n, vector<vector<char>>& grid,vector<vector<int>>& vis){

vis[row][col]=1;

queue<pair<int,int>> q;
q.push({row,col});

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

for(int deltarow=-1;deltarow<=1;deltarow++){
for(int deltacol=-1;deltacol<=1;deltacol++){
int nrow=row+deltarow; //neighbour_row
int ncol=col+deltacol; //neighbour_col

if((abs(deltarow-deltacol)==1) && nrow>=0 && nrow<n && ncol>=0 && ncol<m &&
grid[nrow][ncol]=='1' && vis[nrow][ncol]==0){
vis[nrow][ncol]=1;
q.push({nrow,ncol});
}
}
}

}
}
int numIslands(vector<vector<char>>& grid) {
int n=grid.size();
int m=grid[0].size();
int count=0;

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

for(int row=0;row<n;row++){
for(int col=0;col<m;col++){
if(!vis[row][col] && grid[row][col]=='1'){
count++;
bfs(row,col,m,n,grid,vis);
}
}
}
return count;
}
};

Complexity Analysis​

  • Time Complexity: O(M∗N)O(M*N)
  • Space Complexity: O(M∗N)O(M*N)
  • Where M is the row of the grid.
  • Where N is the col of the grid.

References​