Problem of the day
You are given an N x M integer matrix. Your task is to modify this matrix in place so that if any cell contains the value 0, then all cells in the same row and column as that cell should also be set to 0.
Requirements:
You must do it in place.
For Example:
If the given grid is this:
[7, 19, 3]
[4, 21, 0]
Then the modified grid will be:
[7, 19, 0]
[0, 0, 0]
Input Format:
The first line of the input contains a single integer ‘T’ representing the no. of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the no. of the rows and columns of the matrix.
The next 'N' lines will contain ‘M’ space separated integers representing the elements of the matrix.
Output Format:
For each test case, print the modified grid.
Print output of each test case in a separate line.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints:
1 ≤ T ≤ 1000
1 ≤ m, n ≤ 1000
Σ(m * n) ≤ 2000000
-2^(31) ≤ matrix[i][j] ≤ 2^(31)-1, for all (1 ≤ i ≤ n and 1 ≤ j ≤ m).
Time Limit: 1 sec
Follow up:
Can we do better than O(m * n) space?
Using O(m + n) space is an improvement but we can still do better.
We can do it using constant memory. Can you do it?
2
2 3
7 19 3
4 21 0
3 3
1 2 3
4 0 6
7 8 9
7 19 0
0 0 0
1 0 3
0 0 0
7 0 9
For First Case - Similar to the example explained above.
For Second Case -
Only the cell (2,2) has zero. So all the elements of the second row and second column are changed to zeros.
2
4 2
1 0
2 7
3 0
4 8
3 3
0 2 3
1 0 3
1 2 0
0 0
2 0
0 0
4 0
0 0 0
0 0 0
0 0 0
We can simulate the process described in the statement naively.
The basic idea is to maintain another boolean matrix ‘isZero’ which stores whether our resultant matrix should contain a zero at a particular index or not. We can traverse every element of our original matrix. If the element is 0, then we traverse the complete row and complete column of that particular element and set isZero values accordingly to true for all the elements in that row and column.
Algorithm:
setZeros(matrix)
O(N * M * (M + N)) where N & M are dimensions of the given matrix.
We are traversing each element. For each element that is zero, we are traversing its complete row and column. So we have O(M * N) elements and for each element, we can traverse a row and a column in the worst case, i.e. O(M + N). So total complexity is O(M * N * (M + N).
O(N * M) where N & M are dimensions of the given matrix.
We need to declare a 2D boolean matrix of size n x m. So the total required space will be O(N * M).