Last Updated: 26 Dec, 2021
Count Islands
Moderate
Asked in company
You are given a grid of binary numbers, ‘1’ and ‘0’ where ‘0’ means land and ‘1’ means water. A closed island is a group of ‘0’s surrounded on the 4 sides by water, i.e., ‘1’. Your task is to find the number of islands in the given grid.
For Example:
You are given ‘grid’ = [[1,1,1 ,1 1], [1, 0, 0, 1 1],[ 1, 1, 1, 1,1], [1, 0, 1, 1, 1],[1, 1, 1, 1, 1]], Here the given grid is
We can clearly see that there are 2 islands. Hence the answer is 2.
Input Format:
The first line of input contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the row and column of the grid.
The next ‘N’ lines of each test case contain ‘M’ space-separated integers representing the elements of the grid.
Output Format:
For each test case print a single integer, representing the number of islands in the grid.
Print a separate line of each test case.
Constraints:
1 <= T <= 10
1 <= N, M <= 10^3
grid[i][i] = 0 or 1
Time Limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
In this approach, we see that a ‘0’ could be a part of the island only if its connect by all sides from either ‘1’ or a ‘0’, i.e if a ‘0’ is at the boundary of the grid, then all the ‘0’ connected to it will not be in an island.
Therefore we can start graph traversal from a ‘0’ and its connected component will only be valid if none of its elements lies on the border of the matrix. It is clear that we need to find all the valid connected components.
Therefore from DFS every time we find a ‘1’ we return 1 and if we reach outside the grid we return 0. Then we can multiply the results of each dfs call and check if the current component is valid or not.
We create a DFS(grid, row, col), where grid is the matrix given and row and col are the positions of the current element in the matrix.
Algorithm:
- In the function dfs(grid, row,col):
- If the row is less than 0 or greater than the length of the grid.
- Return 0
- If col is less than 0 or greater than length of grid[0]
- Return 0
- If grid[row][col] is greater than 1
- Return 1
- Set grid[row][col] as 2
- Return dfs(grid, row - 1, col)* dfs(grid, row + 1, col)*dfs(grid,row, col - 1) *dfs(grid,row,col + 1)
- If the row is less than 0 or greater than the length of the grid.
- In the given function
- Set sum as 0
- Iterate i through length of the grid and j through grid[i]
- If grid[i][j] is 0, add dfs(grid, i, j) to sum
- Return sum
In this approach, we will do the same thing of counting all the valid components of the graph, but instead of a depth-first search, we can use the breadth-first search. This method is also called the flood fill method.
We create a bfs(grid, row, col, visited): function, where grid is the given grid, row and col are the position of the current node and visited, is the set of visited nodes.
Algorithm:
- In the bfs(grid, row, col, visited):
- Set visited[row][col] as False
- Set ans as 1
- Initialise an empty array queue, and insert the pair (row, col) in queue
- Iterate (r,c) through queue
- Set directions as an array of all possible next positions from (r, c)
- Iterate (i, j) through directions
- If i is less than 0 or greater than the length of grid, set ans as 0
- Otherwise if, j is less than 0 or greater than the length of grid[0], set ans as 0.
- Otherwise is if grid[i][j] is equal to 0 and visited[i][j] is False
- Set visited[i][j] as True and insert (i, j) in queue
- Return ans
- In the given function
- Create a 2d matrix and initialize to 0. Then if visited[i][j] is 0 then it's not visited otherwise if it's 1 then its already visited, with all values initialized as False
- Iterate i through grid and j through grid[i]
- Set num as i* length of grid + j
- If grid[i][j] is 0 and visited[i][j] is False
- Increase ans by bfs(grid, i, j, visited)
- Return ans