Number of Islands LeetCode Solution


Frequently asked in Adobe Amazon Apple Bloomberg DocuSign Facebook Goldman Sachs Google Indeed LinkedIn lyft Microsoft Oracle Salesforce SAP ServiceNow Uber Yandex
LeetCode LeetCodeSolutions Shopee tiktokViews 8708

Problem Statement

The number of Islands LeetCode Solution – “Number of Islands” states that you are given an m x n 2D binary grid which represents a map of ‘1’s (land) and ‘0’s (water), you have to 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.

Example

Number of Islands LeetCode Solution

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

3

Explanation: We can see the highlighted islands in the figure above. As we can see, there are three islands.

Note: Different colors are denoting different islands in the image above.

Approach

Idea:

We can use any traversal DFS or BFS to solve this problem (Number of Islands LeetCode Solution). We will also maintain an array called “visited” which will keep track of the lands we have already visited. So we will first initialize a variable called “answer” with zero, which will store the number of islands. 

We will traverse all the lands on the grid one by one. While traversing if we find any land which hasn’t been visited yet, then it means we have found a new island and we will increase our “ans” and using DFS or BFS we will mark all the lands which are connected as visited.

Algorithm:

We will maintain an array called “visited” which will maintain 

  1. Initialize a boolean array “visited” with all the values as false. Also, initialize a variable called “ans” with zero to store our answer.
  2. Traverse through each element of the grid.
  3. Check, if it is a land and it has not been visited yet, increase the “ans” by 1 and start any traversal(BFS or DFS) from that element.

Code

C++ Program of Number of Islands:

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool check(int x, int y, int n, int m)
{
   return x >= 0 and y >= 0 and x < n and y < m;
}
void dfs(vector<vector<char>> &grid, vector<vector<bool>> &vis, int x, int y, int n, int m)
{
   if (!check(x, y, n, m) or grid[x][y] == '0' or vis[x][y] == true)
   {
       return;
   }
   vis[x][y] = true;
   for (auto ele : dir)
   {
       int x1 = x + ele.first;
       int y1 = y + ele.second;
       dfs(grid, vis, x1, y1, n, m);
   }
}
int numIslands(vector<vector<char>> &grid)
{
   int ans = 0;
   int n = grid.size();
   int m = grid[0].size();
   vector<vector<bool>> vis(n, vector<bool>(m, false));
   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j < m; j++)
       {
           if (vis[i][j] == false and grid[i][j] == '1')
           {
               ans++;
               dfs(grid, vis, i, j, n, m);
           }
       }
   }
   return ans;
}
int main()
{
   vector<vector<char>> grid = {
       {'1', '1', '0', '0', '0'},
       {'1', '1', '0', '0', '0'},
       {'0', '0', '1', '0', '0'},
       {'0', '0', '0', '1', '1'}};
   cout << numIslands(grid) << endl;
   return 0;
}

3

JAVA Program of Number of Islands:

public class TutorialCup
{
    static int dir[][]={{-1,0},{0,-1},{1,0},{0,1}};
    public static boolean check(int x,int y,int n,int m){
        return x>=0 && y>=0 && x<n && y<m;
    }
    public static void dfs(char[][] grid,boolean vis[][],int x,int y,int n,int m ){
        if(!check(x,y,n,m) || grid[x][y]=='0' || vis[x][y]==true){
            return;
        }
        vis[x][y]=true;
        for(int i=0;i<4;i++){
            int x1=x+dir[i][0];
            int y1=y+dir[i][1];
            dfs(grid,vis,x1,y1,n,m);
        }
    }
    public static int numIslands(char[][] grid) {
        int ans=0;
        int n=grid.length;
        int m=grid[0].length;
        boolean vis[][]=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(vis[i][j]==false && grid[i][j]=='1'){
                    ans++;
                    dfs(grid,vis,i,j,n,m);
                }
            }
        }
        return ans;
    }
  public static void main(String[] args) {
    char grid[][]={
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}};
        System.out.println(numIslands(grid));
  }
}

3

Complexity Analysis for Number of Islands LeetCode Solution

Time Complexity for Number of Islands LeetCode Solution

The time complexity of the above code is O(n*m) because we are traversing each element of the grid always once. Here n and m are the numbers of rows and number of columns respectively.

Space Complexity for Number of Islands LeetCode Solution

The space complexity of the above code is O(n*m) because we are using a 2D array to store whether we have visited a land or not.

Reference – https://en.wikipedia.org/wiki/Breadth-first_search

Translate »