## Set matrix’s row and col to zero

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

My initial thoughts:

1. Scan the matrix, store the numbers of rows and columns that will be set to zero to two sets
2. Iterate through those two sets and set corresponding row and col to zeros.

My initial codes:

```	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;
}
}
}

Comments after running:

It works fine.
Time complexity O(M*N) and space complexity O(M+N).

Solutions:
The idea of the solution is similar to mine but it use two arrays to store the row and col numbers. Supposedly, this should use less memory than using java.util.Set. I improved the solution a little bit by utilizing boolean vectors:
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;
}
}

If we assume the size of the matrix is not that big, we can, again, use bit-vector, which is constant memory complexity:
int rowMask = 0, colMask = 0;
for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix[0].length; ++j) {
if(matrix[i][j] == 0) {
rowMask |= (1 << i);
colMask |= (1 << j);
}
}
}

for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix[0].length; ++j) {
if( (rowMask & (1 << i)) != 0 ||
(colMask & (1 << j)) != 0 )
matrix[i][j] = 0;
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5bcfc3a755879', {
sectionId: '370373',
format: 'inread'
});
});

Advertisements

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5bcfc3a7558a9',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5bcfc3a7558ab',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Like this:Like Loading...

Related
```