# My O(1) java solution

• The basic idea is scan the matrix three times, the first time only mark the row be a special value if found 0, the second time only mark the column be a special if found 0, the third convert all special value to 0.

Even though we mark the whole row/column be a special value when we found 0, it still an O(N) time complexity scan because if we found 0, we just mark the whole row/column be the special value and break immediately.

``````public void setZeroes(int[][] matrix) {
int row=matrix.length;
if(row==0) return;
int col=matrix[0].length;
if(col==0) return;
// mark rows
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
if(matrix[i][j]==0){
for(int z=0;z<col;z++)
if(matrix[i][z]!=0) matrix[i][z]=Integer.MIN_VALUE/123;
break;
}
// mark by columns
for(int i=0;i<col;i++)
for(int j=0;j<row;j++)
if(matrix[j][i]==0){
for(int z=0;z<row;z++)
if(matrix[z][i]!=0 && matrix[z][i]!=Integer.MIN_VALUE/123)
matrix[z][i]=Integer.MIN_VALUE/123;
break;
}
// convert
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
if(matrix[i][j]==Integer.MIN_VALUE/123) matrix[i][j]=0;
}``````

• This is a hack. What if your matrix has special value?

• It's actually easy to solve. You can scan the whole matrix at the beginning, find the max and the min item, then use either (max+1) or (min-1) as the special value.

• Fair enough. You need an extra scan to pick 'special value' that is not in the matrix.

• I thought of find max and min too, but there is still problem. What if the matrix contains all the Integer? You just can't find such a unique value. This algorithm is not sound.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.