Count Good Islands

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
Celebal Technologies

Problem statement

You are given two matrices, ‘MATRIX1’ and ‘MATRIX2’ of size ‘M’ x ‘N’ having 0s and 1s only, where ‘0’ in the matrix represents water, and ‘1’ in the matrix represents the land. An island is a group of 1s connected horizontally and vertically. An island in ‘MATRIX2’ is considered to be good if there is an island in ‘MATRIX1’ that contains all the cells that make up this island in ‘MATRIX2’. You have the find the count of good islands.

For example : 
Let ‘MATRIX1’ be : 
1 1
0 0

Let ‘MATRIX2’ be: 
1 1
0 0

All the 1s present in ‘MATRIX2’ can be considered a good island. There is 1 good island present.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M’ and ‘N’, representing the size of the matrices.

The next ‘M’  lines of each test case contain ‘N’ space-separated integers, representing the cells of ‘MATRIX1’.

The next ‘M’  lines of each test case contain ‘N’ space-separated integers, representing the cells of ‘MATRIX2’.
Output Format : 
For each test case, print the number of good islands.

Print output of each test case in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= M, N <= 10^3
0 <= MATRIX1[i][j], MATRIX2[i][j] <= 1

Time Limit: 1 sec
Sample Input 1 :
2
4 2
1 0
0 0
1 0
0 1
1 0
0 1
1 0
1 1    
2 2
1 1
0 0
1 1
0 0
Sample Output 1 :
1
1
Explanation For Sample Input 1 :
For test case 1: 
‘MATRIX1’ : 
1 0
0 0
1 0
0 1

‘MATRIX2’ : 
1 0
0 1
1 0
1 1

The 1 present at the top left corner can be considered as a good island since 'MATRIX1' also has 1 at that position. But for the other islands in 'MATRIX2', the corresponding cells in 'MATRIX1' do not have an island. So the number of the good islands is 1.

For test case 2: 
‘MATRIX1’ : 
1 1
0 0

‘MATRIX2’ : 
1 1
0 0

All the 1s present in ‘MATRIX2’ can be considered a good island. There is 1 good island present.
Sample Input 2 :
2
1 1 
0
1
5 5
1 0 1 0 1
1 1 1 1 1
0 0 0 0 0
1 1 1 1 1
1 0 1 0 1
0 0 0 0 0
1 1 1 1 1 
0 1 0 1 0
0 1 0 1 0
1 0 0 0 1
Sample Output 2 :
0
2
Hint

Try to find 1s present in ‘MATRIX2’ while checking in ‘MATRIX1’ recursively.

Approaches (2)
Depth-First Search

The basic idea is to find the ‘1’ present in ‘MATRIX2’ which is not visited yet and then recursively traverse all the cells present on that island while checking for the ‘1s’ present in the ‘MATRIX1’ at the same position or not. If all the cells of an island in ‘MATRIX2’ are present in the ‘MATRIX1’, we count it as a good island. We also change the value of visited cells to ‘-1’ so we don’t traverse them again.

 

Here is the algorithm :

 

  1. Create a variable (say, ‘ANS’) that will store the number of good islands and initialize it with 0.
  2. Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse all the rows.
    • Run a loop from 0 to ‘N’ (say, iterator ‘j’) to traverse all the columns
      • Check if ‘MATRIX2[i][j]’ is equal to 1.
        • Create a variable (say, ‘GOOD’) to check whether the island is good or not and initialize it with ‘true’.
        • Call the DFS function on the current position to check for the cells on the island.
        • Check if ‘GOOD’ is ‘true’, update ‘ANS’ by 1.
  3. Return ‘ANS’.

 

DFS(‘M’, ‘N’, ‘MATRIX1’, ‘MATRIX2’, ‘i’, ‘j’, ‘GOOD’)  (where ‘M’ and ‘N’ are the size of the matrices, ‘MATRIX1’ and ‘MATRIX2’ are the given matrices, ‘i’ and ‘j’ are starting position, and ‘GOOD’ is for checking the validity of good island).

 

  1. Base case:
    • Check if ‘i’ is smaller than 0 or greater than equal to ‘M’ or ‘j’ is smaller than 0 or greater than equal to ‘N’ or ‘MATRIX2[i][j]’ is not equal to 1.
      • Return.
  2. Mark ‘MATRIX2[i][j]’ as visited by updating the cell’s value to ‘-1’.
  3. Check if value of ‘MATRIX1[i][j]’ is equal to 0.
    • Update ‘GOOD’ to ‘false’.
  4. Traverse in all 4 directions of the matrix by updating ‘i’ and ‘j’.
Time Complexity

O(M*N), where ‘M’ and ‘N’ are the size of the matrix.

 

We traverse all the cells of both the matrices only once using recursion. Therefore, the overall time complexity will be O(M*N).

Space Complexity

O(M*N), where ‘M’ and ‘N’ are the size of the matrix.

 

The recursion stack can contain at most ‘M’ * ‘N’ cells of the matrix. Therefore, the overall space complexity will be O(M*N).

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