## Sunday, November 25, 2012

### [leetcode] Set Matrix Zeroes

Problem Description:
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
It is the same problem as that in the book Cracking the Coding Interview Question 1.7
At first glance, a quick solution coming to mind maybe using two arrays to record the rows and columns that should be set to zeros respectively. And this solution needs O(m+n) space. As suggested by leetcode OJ , can we use constant space ?

Well, yes we can. The tricky part is that we use the first column and the first row of the input matrix to record the rows and columns that needs to set zero. Another point is that since the 1st row and 1st column are intersected at cell (0,0), so matrix=0 can't tell us the 1st row or 1st column or both need to be set 0. In my implementation, I use two extra variable firstLine and firstCol to record it.

Here's the code, well, I concede it's a little messy. If there's other neat way to do it, I will appreciate it if you let me know.

```public class Solution {
public void setZeroes(int[][] matrix) {
int firstLine = 1;
int firstCol = 1;
//set the first row and first column to record the rows and cols to be set 0s.
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix.length;j++){
if(matrix[i][j]==0){
if(i==0)
firstLine=0;
if(j==0)
firstCol=0;
matrix[j]=0;
matrix[i]=0;
}
}
}
//set rows and columns
for(int i=1;i<matrix.length;i++){
if(matrix[i]==0){
for(int j=1;j<matrix.length;j++)
matrix[i][j]=0;
}
}
for(int j=1;j<matrix.length;j++){
if(matrix[j]==0){
for(int i=1;i<matrix.length;i++)
matrix[i][j]=0;
}
}
//set first row and column
if(firstLine==0){
for(int j=0;j<matrix.length;j++)
matrix[j]=0;
}
if(firstCol==0){
for(int i=0;i<matrix.length;i++)
matrix[i]=0;
}
}
}
```