Number of Islands

Easy
0/40
10 upvotes
Asked in companies
InfosysMicrosoftMeesho

Problem statement

You have been given a non-empty grid consisting of only 0s and 1s. You have to find the number of islands in the given grid.

An island is a group of 1s (representing land) connected horizontally, vertically or diagonally. You can assume that all four edges of the grid are surrounded by 0s (representing water).

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two single space-integers ‘N’ and ‘M’ representing the number of rows and columns of the grid, respectively.

From the second line of each test case, the next N lines represent the rows of the grid. Every row contains M single space-separated integers.
Output Format: 
For each test case, the only line of output will print the number of islands in the grid.

Print the output of each test case in a separate line.

Note: You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 100
1 <= M <= 100
0 <= grid[i][j] <= 1

Time limit: 1 sec
Sample Input 1:
2
4 5
0 0 1 1 0
1 0 1 1 0
0 1 0 0 0 
0 0 0 0 1
1 3
1 1 1
Sample output 1:
2
1
Explanation of Sample output 1:
For the first test case, there are two islands in the grid.

For the second test case, there is only one island in the grid.
Sample Input 2:
2
1 5
0 0 0 0 0
4 4
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
Sample output 2:
0
1
Hint

Can you think of a recursive solution? Start from a land cell and visit all its neighbour cells.

Approaches (2)
DFS

The problem boils down to find the number of connected components in the grid. 

 

If we are on a land cell and explore every cell connected to it 8-directionally (and recursively cells connected to those cells, and so on), then the total number of cells with land explored will be one island.

 

To ensure we don't count cells in the island more than once, we will mark 1(land) as 0 during the recursion call.

 

Here is the algorithm:

We have a function ‘numberOfIsland’ in which we are iterating over the whole grid.

 

We will initialise ‘islands’ to 0 to count the number of islands. Whenever we encounter a 1(land), we will call ‘dfs’ and increment ‘islands’ by 1. 

 

The ‘dfs’ function works as follows:

  1. If indices are out of bound or the value present at the current cell is 0, then simply return 0.
  2. Else, Mark the cell as 0, so that we don’t count cells in an island more than once and call the ‘dfs’ function in 8-directions.
Time Complexity

O(N * M), where N is the number of rows in the given grid, and M is the number of columns. 

 

We are visiting every cell once. Hence, the time complexity is O(N * M).

Space Complexity

O(N * M), where N is the number of rows in the given grid, and M is the number of columns. 

 

In the worst case, when the grid is filled with 1s, space used by call stack during recursion can go up to O(N * M).

Code Solution
(100% EXP penalty)
Number of Islands
Full screen
Console