Find the Good Matrix

Moderate
0/80
Average time to solve is 30m
19 upvotes
Asked in companies
AppleGrowwFlipkart

Problem statement

You have given a 2-dimensional array ‘ARR’ with ‘N’ rows and ‘M’ columns in which each element contains only two values,i.e., 0 and 1. Your task is to convert the given matrix into the Good matrix in which if an element is 0, you need to set all elements values present in its entire row and column to 0.

For example:

Consider ARR = [[1 , 0 , 1] ,
                [1 , 1 , 1] , 
                [1 , 1 , 1]], 
the Good matrix after updating the given matrix as described in the question is  
                [[0 , 0 , 0] , 
                 [1 , 0 , 1] , 
                 [1 , 0 , 1]]. 
Since ARR[0][1] is 0, we need to set all element’s values present in 0-th row and 1-th column to 0.

Note :

You do not need to print the matrix. Just change in the given input.
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two integers, 'N' and ‘M’, denoting the number of rows and columns in the array.
The Next 'N' lines of each test case contain 'M' space-separated integers denoting the elements of the array 'ARR'.
Output format :
For each test case, return the Good matrix after updating the given matrix as described in the question.

Print the output of each test case in a separate line
Constraints :
1 <= T <= 20
1 <= N <= 300
1 <= M <= 300

ARR[i][j] can only contain two values, i.e, 0 and 1.    

 Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of rows and the number of columns in the array ‘ARR’ respectively, and 'ARR[i][j]' denotes the ’j-th’ element of  'i-th' row of the array 'ARR'. 

Time Limit: 1sec
Sample Input 1 :
2
2 2 
0 1 
1 1
3 3
1 1 0
1 1 1 
1 1 1
Sample Output 1 :
0 0
0 1
0 0 0
1 1 0
1 1 0
Explanation of sample input 1:
For the first test case, 
The Good matrix after updating the given matrix as described in the question is  
                    [[0 , 0] , 
                     [0 , 1]]. 
Since ARR[0][0] is 0, we need to set all elements value present in 0-th row and 0-th column to 0.

For the second test case,
The Good matrix after updating the given matrix as described in the question is  
                    [[0 , 0 , 0] , 
                     [1 , 1 , 0] , 
                     [1 , 1 , 0]]. 
Since ARR[0][2] is 0, we need to set all elements value present in 0-th row and 2-th column to 0.
Sample Input 2 :
2
4 4 
1 1 1 1   
0 1 1 1
1 1 1 1
0 1 1 1
3 3
0 1 1
0 1 1 
1 1 1
Sample Output 2 :
0 1 1 1
0 0 0 0
0 1 1 1
0 0 0 0
0 0 0
0 0 0
0 1 1
Hint

Try to think of an approach by creating a 2-dimensional array to convert the given matrix into the Good matrix.

Approaches (3)
Brute Force

A simple method is to create a 2-dimensional array to store the changes we need to update in the original matrix to convert the given matrix into the Good matrix.
 

Our approach will be to create a 2-dimensional array answer with N rows and M columns, and we will copy all elements value present in the matrix ARR into the matrix answer. We will iterate the variable row from 0 to N - 1, and in each iteration, we will iterate col from 0 to M - 1.

  1. We will check if ARR[row][col] is equal to 0, then we need to set all elements value in the entire row and column of ARR[row][col] to 0. We will iterate index from 0 to N - 1, and set answer[index][col] as 0.
  2. We will iterate index from 0 to M - 1, and set answer[row][index] as 0.

 

In the end, the matrix answer is the Good matrix which we will get after updating the given matrix as described in the question. We will return the matrix answer.

 

Algorithm:
 

  • Create a 2-dimensional array answer with N rows and M columns, which we will use to convert the given matrix into the Good matrix. We will update the changes in the matrix answer.
  • Copy all elements value present in the array ARR into the array answer.
  • Iterate row from 0 to N - 1.
    • Iterate col from 0 to M - 1.
      • Check if ARR[row][col] is equal to 0.
        • Iterate index from 0 to N - 1, and set answer[index][col] as 0.
        • Iterate index from 0 to M - 1, and set answer[row][index] as 0.
  • Return the matrix answer.
Time Complexity

O(N * M * (N + M)), where N and M denote the number of rows and columns in the array.
 

In the worst case, we are doing N * M iteration, and in each iteration, it takes O(N + M) to update the changes as described in the question to find the Good matrix. Hence, the overall Time Complexity  = O(N * M) * (N + M) =  O(N * M * (N + M)).

Space Complexity

O(N * M), where N and M denote the number of rows and columns in the array.
 

The Space Complexity O(N * M) is used to create a 2-dimensional array to store the changes we need to update in the given matrix to convert the given matrix into the Good matrix. Hence, the overall Space Complexity is O(N * M).

Code Solution
(100% EXP penalty)
Find the Good Matrix
Full screen
Console