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)

Below mentioned solution should work on both the platforms.

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.

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;
    }
};
Number of Islands Solution InterviewBit LeetCode
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)

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.

Share your love

Leave a Reply