Number of Islands

You are given a 2D grid of 1's and 0's where 1's denotes the land and 0's denote the water. You need to return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands either vertically or horizontally. You can assume that all the four edges of the given grid are surrounded by water.

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

Expected output: 3.
Explanation: There are 3 islands in total where all the lands (1's) are connected either horizontally or vertically.

Algorithm

The problem can be solved using depth first search technique. You need to traverse the entire grid. For each position, if the element is 1, then take that position as the starting point and start a DFS traversal. For a valid island, it returns 1. Keeep a count of all such islands and return the final answer.

In the DFS method, if the element is not valid for traversal i.e if the position coordinates is not valid or the element is 0, return 0. Else, mark the current element as 0 (visited) and perform recursive call on the neighbouring 4 elements with coordinates (i+1, j), (i-1, j), (i, j+1) and (i, j-1) and then return 1.

For a better understanding, look at the code below.

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

int dfs(vector<vector<char>> & grid, int i, int j){
    if(i < 0 || j < 0 || i >= grid.size() || j >= grid[i].size() || grid[i][j]=='0'){
        return 0;
    }
    grid[i][j]='0';
    dfs(grid, i+1, j);
    dfs(grid, i-1, j);
    dfs(grid, i, j+1);
    dfs(grid, i, j-1);
    return 1;
}

int numIslands(vector<vector<char>>& grid) {
    if(grid.size()==0){
        return 0;
    }
    int ans=0;
    for(int i=0; i<grid.size(); i++){
        for(int j=0; j<grid[i].size(); j++){
            if(grid[i][j]=='1'){
                ans+=dfs(grid, i, j);
            }
        }
    }
    return ans;
}

int main(){
	vector<vector<char>> grid(4, vector<char>(5));
	grid = {{'1', '1', '0', '0', '0'},
			 {'1', '1', '0', '0', '0'},
			 {'0', '0', '1', '0', '0'},
			 {'0', '0', '0', '1', '1'}};
	cout<<"The total number of islands are: "<<numIslands(grid);
	return 0;
}

Also, check out another popular interview problem Product of array except self.

One comment

Leave a Reply

Your email address will not be published.