This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/set-matrix-zeros-problem/.
Problem
Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0
Example
Input :1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
Output :
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0
Solution
Method 1 - Using the extra space and O(n^2) solution
In this approach we can do :
- Scan the matrix, store the numbers of rows and columns that will be set to zero to two sets
- Iterate through those two sets and set corresponding row and col to zeros.
public static void setZero(int[][] matrix) {
Set<Integer> rowToClear = new HashSet<Integer>();
Set<Integer> colToClear = new HashSet<Integer>();
for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix[0].length; ++j) {
if(matrix[i][j] == 0) {
rowToClear.add(i);
colToClear.add(j);
}
}
}
for(Integer row : rowToClear) {
for(int j = 0; j < matrix[row].length; ++j) {
matrix[row][j] = 0;
}
}
for(Integer col : colToClear) {
for(int i = 0; i < matrix.length; ++i) {
matrix[i][col] = 0;
}
}
}
Time complexity - O(M*N) and space complexity O(M+N).
Also, as SET takes more space, rather than using SET, we can use a simple boolean arrays.
boolean[] rowBooleanVectors = new boolean[matrix.length];
boolean[] colBooleanVectors = new boolean[matrix[0].length];
for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix[0].length; ++j) {
if(matrix[i][j] == 0) {
rowBooleanVectors[i] = true;
colBooleanVectors[j] = true;
}
}
}
for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix[0].length; ++j) {
if( rowBooleanVectors[i] || colBooleanVectors[j])
matrix[i][j] = 0;
}
}
Time complexity - O(M*N) and space complexity O(M+N).
Method 2 - Space efficient and O(n^2) solution
This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays rowBooleanArray[] and colBooleanArray[] of method 1.
So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary.
We now need 2 passes.
I use 1rst column and first row as markers to know where are rows/cols with only 1's. Then, there are 2 variables l and c to remember if 1rst row/column are all 1's also. So the first pass sets the markers and resets the rest to 0's.
The second pass sets 1 in places where rows and cols where marked to be 1, and resets 1st line/col depending on l and c.
arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).
1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 0s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 0s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.
Here is the code:
N = matrix.length;
M = matrix[0].length;
// pass 1
// 1 rst line/column
int c = 1
for(int i = 0; i < N; ++i) {
c &= matrix[i][0]
}
l = 1
for(int j = 0; j < M; ++j) {
l &= matrix[0][i]
}
// other line/cols
// use line1, col1 to keep only those with 1
for(int i = 1; i < N; ++i) {//start iterating with 1
for(int j = 1; j < M; ++j) {
if (matrix[i][j] == 0){
matrix[0][j] = 0
matrix[i][0] = 0
}
else
matrix[i][j] = 0
}
}
// pass 2
// if line1 and col1 are ones: it is 1
for(int i = 1; i < N; ++i){
for(int j = 1; j < M; ++j) {
if( matrix[i][0] & matrix[0][j] == 1)
matrix[i][j] = 1
}
}
// 1rst row and col: reset if 0
if (l == 0){
for(int i = 0; i < N; ++i) {
matrix [i][0] = 0
}
}
if (c == 0){
for(int j = 1; j < M; ++j) {
matrix [0][j] = 0
}
}
print(matrix);
Time Complexity: O(M*N)
Auxiliary Space: O(1)
Reference
0 comments:
Post a Comment