Last Updated: 18 Feb, 2021
Zero Matrix
Easy
Asked in companies
You are given a matrix 'MATRIX' of dimension 'N' x 'M'. Your task is to make all the elements of row 'i' and column 'j' equal to 0 if any element in the ith row or jth column of the matrix is 0.
Note:
1) The number of rows should be at least 1.
2) The number of columns should be at least 1.
3) For example, refer to the below matrix illustration:
Input Format:
The first line contains two space-separated integers, 'N' and 'M', as described in the problem statement.
The next 'N' lines contain 'M' integers separated by spaces describing rows of the matrix.
Output Format:
Return 'N' rows consisting of 'M' integers representing the matrix.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= N <= 100
1 <= M <= 100
-10^9 <= MATRIX[i][j] <= 10^9
Where 'MATRIX[i][j]' denotes the matrix element.
Follow Up:
Can you solve it with the space complexity of O(1)?
Time limit: 1 sec
Approaches
We can use two vectors of datatype bool of size ‘N’ and ‘M’, let say ‘ROW’ and 'COL' respectively.
The steps are as follows:
- Initialize both the vectors with the false.
- We are aiming to change the entry of the vector from false to true if we found any element which is 0 in that row for the ‘ROW’ vector and column for the 'COL' vector.
- Run a loop to N times for the ‘ROW’, in each iteration:
- Run a loop to M times for the entries in that ‘ROW’, in each iteration:
- If ‘MATRIX[i][j]' is 0, then mark ‘ROW[i]' = true and ‘COL[j]’ = true because we have to set entire ith row and entire jth column of the matrix ‘MATRIX’ to 0, where 0 <= ‘i’ < ‘N’ and 0 <= ‘j’ < ‘M’ and ‘i’ is for row and ‘j’ is for column.
- Run a loop to M times for the entries in that ‘ROW’, in each iteration:
- After the completion of the above steps, the ‘ROW’ vector contains true for those for which we have to set the entire row 0, and the 'COL' vector contains true for those for which we have to set the entire column 0.
- Again, run a loop to ‘N’ times for the ‘ROW’, in each iteration:
- Run a loop to ‘M’ times for the entries in that ‘ROW’, in each iteration:
- If ‘ROW’[i]' = true or ‘COL[j]’ = true, then set ‘MATRIX[i][j]' = 0.
- Else, leave ‘MATRIX[i][j]' as it is.
- Run a loop to ‘M’ times for the entries in that ‘ROW’, in each iteration:
- Finally, return the matrix ‘MATRIX’.
We can use the 1st row and 1st column which means the 1st cell of every row and column as an indicator. ‘MATRIX[0][0]’ will tell us whether we have to set the entire 1st row to be zero or not, and a bool variable ‘ISCOLZERO’ will tell us the same for the entire 1st column.
The steps are as follows:
- Initialize ‘ISCOLZERO’ to false.
- Run a loop to ‘N’ times for the row, in each iteration:
- First check, if ‘MATRIX[i][0]’ is 0, then ‘ISCOLZERO’ = true. Because we have found a 0 in the 1st column so we have to set the entire 1st column to be 0.
- Run a loop to iterate from the second column of that row, in each iteration (not from the 1st column because if we start the loop from the 1st column and let us suppose 2nd-row 1st-column entry is 0, then we are setting ‘MATRIX[0][0]’ to 0 which also implies that we have to set the entire 1st row to be 0, but here we found a 0 entry in a column so no need to set 1st row to be 0) :
- If ‘MATRIX[i][j]’ is 0, then mark ‘MATRIX[i][0]’ = 0 (because we have to set that entire row to be 0) and ‘MATRIX[0][j]’ = 0 (because we have to set that entire column to be 0).
- Run a loop from the second row, in each iteration:
- Run a loop from the second column, in each iteration (As we are dealing with the 1st row and 1st column separately so we are starting the loop from the 2nd row and column) :
- If ‘MATRIX[i][0]’ is 0 or ‘MATRIX[0][j]’ is 0, then set ‘MATRIX[i][j]’=0.
- Else, leave ‘MATRIX[i][j]’ as it is.
- Run a loop from the second column, in each iteration (As we are dealing with the 1st row and 1st column separately so we are starting the loop from the 2nd row and column) :
- After completion of the above iterations, we have successfully set the matrix from ‘MATRIX[1][1]’ onward to 0 if required.
- If ‘MATRIX[0][0]’ is 0, then we have to set the entire 1st row to be 0 so,
- Run a loop to ‘M’ times, in each iteration:
- Set ‘MATRIX[0][j]’ = 0
- Run a loop to ‘M’ times, in each iteration:
- If ‘ISCOLZERO’ is true, then we have to set the entire 1st column to be 0 so,
- Run a loop to ‘N’ times, in each iteration:
- Set ‘MATRIX[i][0]’ = 0
- Run a loop to ‘N’ times, in each iteration:
- Finally, return the matrix ‘MATRIX’ row-wise.
Similar problems