Number of Islands Solution InterviewBit LeetCode

Number of Islands is a classic interview question asked in most of the interview questions. It’s a very frequent interview question that can test your knowledge of Depth First Search and Breadth-First Search.

Question: Number Of Islands

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.

Example 1:

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

Example 2:

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

Solution: (InterviewBit and LeetCode)

Let us discuss the algorithm and the working code for the most optimized code in Python and C++.

Algorithm:

For the above problem, to solve this question we are using Depth First Search. In this, we are going through all the grids which represent ‘1’. Once we receive ‘0’ on all the sides of a given grid location we increase the count to plus 1 for the number of islands found.

Depth First Search is only performed only when we encounter 1 in the Grid. If initially ‘0’ is encountered then no Depth First Search is performed and we move to the next item in the Grid.

//C++ Code Example
class Solution {
public:
    void dfs(vector<vector<char>> &grid, int i, int j){
        if(i<0 || j<0) return;
        if(i>=grid.size() || j>=grid[i].size()) return;
        if(grid[i][j]=='1'){
            grid[i][j] = '0';
            dfs(grid,i,j+1);
            dfs(grid,i+1,j);
            dfs(grid,i,j-1);
            dfs(grid,i-1,j);
        }else return;
    }
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0) return 0;
        int res = 0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]=='1'){
                    dfs(grid,i,j);
                    res++;
                }
            }
        }
        return res;
    }
};
#Python Code Example
def numIslands(self, grid):
    if not grid:
        return 0
        
    res = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                self.dfs(grid, i, j)
                res += 1
    return res
def dfs(self, grid, i, j):
    if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
        return
    grid[i][j] = '#'
    self.dfs(grid, i+1, j)
    self.dfs(grid, i-1, j)
    self.dfs(grid, i, j+1)
    self.dfs(grid, i, j-1)
Number of Islands Solution InterviewBit LeetCode

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.

Leave a Comment