# Is there any Constant Space Solution With just One Pass?

• I used 2 arrays to store row and column numbers. Then loop through the matrix and remember 0's row/column indexes. Finally loop through matrix again to fill in 0. The space complexity is O(row + column) and time complexity is O(2*n), n = size of matrix.

I do not post my solution since it is similar to other people. Does anyone try to solve this problem via constant space and O(n) time? Even though I doubt if such solution can be found, it is high possible to be asked to optimize this solution in an interview, I guess.

• I think this is exactly what you are looking for. My solution is One Pass with O(1) space.
I had a hard time to explain how it works to the friend of mine, it really does just one traversal and sets each cell to 0 only one time, except when it set entire row, which was marked as "set to 0s".

``````void setZeroes(vector<vector<int> > &matrix) {

if (matrix.empty()) return;
int M = matrix.size();
int N = matrix[0].size();

int row=-1;
bool markThisRow=false;

for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
if(matrix[i][j] == 0){
// for each 0-cell set all cells on top of it to 0s (this will be done only once, if there were no 0s in this column before)
for(int k=i-1; k>=0; k--)           { matrix[k][j] = 0; }

markThisRow=true; // say "this Row need to be set to 0s"
}else{
// set current cell to 0 only if cell on top of it is 0
if(i>0 && (matrix[i-1][j] == 0))    { matrix[i][j] = 0; }
}
}

// if "previous" Row was marked - set that row to 0s
if(markThisRow) {
if(row >= 0) { setRow(matrix,row); }
row=i; // set index of the current Row to set it later.
markThisRow=false;
}
}

// here we go, after all row has index of the latest row marked, so set all cell of it to 0s
if(row >=0 ) setRow(matrix, row);
}

void setRow(vector<vector<int> > &m, int i){
for(int j=0; j<m[i].size(); j++)    m[i][j]=0;
}``````

• I think I can understand your hard time in explaining to your friend about it. Cool solution!

• I think your solution has problem.
After you set the current row as all Zero. When you go to the next row, it will check whether matrix[i-1][j]==0. But actually, even matrix[i-1][j]==0, it doesn't means matrix[i-1][j] is originally zero, it may be set zero after one zero found in i-1 row.