Count Islands

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
Google inc

Problem statement

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

SI1

We can clearly see that there are 2 islands. Hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
5 5
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
3 4
1 1 1 1
1 0 0 1
1 1 1 1
Sample Output 1:
2
1
Explanation:
For the first test case, ‘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

SI1

We can clearly see that there are 2 islands, Hence the answer is 2.

For the second test case, ‘ ‘grid’ = [[1,1,1 ,1], [1, 0, 0, 1 ],[ 1, 1, 1, 1]], Here the given grid is

SI1

We can clearly see that there are 1 island. Hence the answer is 1.
Sample Input 2:
2
2 3
1 0 1
1 0 1
3 3
1 1 1
0 0 0
1 1 1
Sample Output 2:
0
0
Hint

Try to look at the grid as a graph.

Approaches (2)
DFS

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)
  • 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

 

Time Complexity

O(N*M), Where N and M are the rows and columns of the grid.

 

We are performing a dfs on the grid, in which we will traverse over every element of the grid once. Hence the final time complexity is O(N*M).

Space Complexity

O(N*M), Where N and M are the rows and columns of the grid.

 

The recursion stack in dfs is directly proportional to the number of nodes in the graph, here in the worst case all the elements in the grid can be the nodes. Hence the overall space complexity is O(N*M).

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