Last Updated: 9 Nov, 2020
Number of Islands
Easy
Asked in companies
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).
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
Approaches
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:
- If indices are out of bound or the value present at the current cell is 0, then simply return 0.
- 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.
We can also use breadth-first search technique to explore an island.
The ‘bfs’ function works as follows:
- We will create a queue and put the indices of the current cell (land only) in it.
- We will loop until the size of the queue becomes zero.
- We will pop the front cell of the queue.
- Then, we push the indices of the 8-direction adjacent cells (only land) into the queue.
- To ensure we don’t push a cell again, we will mark the land cells as 0.