# Leetcode: Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

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?

```public void setZeroes(int[][] matrix) {
//to achieve constant space, we need to use the space of the first row and first col
//to store information
if(matrix==null||matrix.length==0||matrix[0].length==0){
return;
}

//1. determine if the first row needs to be set zero because of itself
//which means are there any zeros in the first row
boolean zeroFirstRow = false;
for(int i=0;i<matrix[0].length;i++){
if(matrix[0][i]==0){
zeroFirstRow=true;
break;
}
}
//2. determine if the first col needs to be set zero because of itself
//which means are there any zeros in the first col
boolean zeroFirstCol = false;
for(int i=0;i<matrix.length;i++){
if(matrix[i][0]==0){
zeroFirstCol=true;
break;
}
}
//3. then we can use the first row and first col to store the information of
//the rest elements
for(int i=1;i<matrix.length;i++){
for(int j=1;j<matrix[0].length;j++){
if(matrix[i][j]==0){
matrix[0][j]=0;
matrix[i][0]=0;
}
}
}
//4. set the matrix to zero according to the information stored in the first row and first col
for(int i=1;i<matrix.length;i++){
for(int j=1;j<matrix[0].length;j++){
if(matrix[0][j]==0||matrix[i][0]==0){
matrix[i][j]=0;
}
}
}
//set the first row
if(zeroFirstRow){
for(int i=0;i<matrix[0].length;i++){
matrix[0][i]=0;
}
}
//set the first col
if(zeroFirstCol){
for(int i=0;i<matrix.length;i++){
matrix[i][0]=0;
}
}
}```
Share