Set Matrix Zeroes
Source
Given a m x n matrix, if an element is 0, set its entire row and column to 0.
Do it in place.
Example
Given a matrix
[
[1,2],
[0,3]
],
return
[
[0,2],
[0,0]
]
Challenge
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Java
public class Solution {
public void setZeroes(int[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return;
int m = matrix.length;
int n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(matrix[i][j]==0){
row[i]=true;
col[j]=true;
}
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(row[i]==true || col[j]==true){
matrix[i][j]=0;
}
}
}
}
}
public class Solution {
public void setZeroes(int[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return;
int rownum = matrix.length;
int colnum = matrix[0].length;
boolean hasZeroFirstRow = false, hasZeroFirstColumn = false;
for (int j = 0; j < colnum; ++j) {
if (matrix[0][j] == 0) {
hasZeroFirstRow = true;
break;
}
}
for (int i = 0; i < rownum; ++i) {
if (matrix[i][0] == 0) {
hasZeroFirstColumn = true;
break;
}
}
for (int i = 1; i < matrix.length; ++i) {
for (int j = 1; j < matrix[0].length; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < matrix.length; ++i) {
for (int j = 1; j < matrix[0].length; ++j) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
}
}
if (hasZeroFirstRow) {
for (int j = 0; j < colnum; ++j) {
matrix[0][j] = 0;
}
}
if (hasZeroFirstColumn) {
for (int i = 0; i < rownum; ++i) {
matrix[i][0] = 0;
}
}
}
}