# [leetcode] Set Matrix Zeroes

### 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.

Follow up: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?

```class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
//o(mn) in time, o(mn) in space solution is trivial. Just allocate another m*n matrix as our destnation matrix
//All the stories happen in it. And we copy the destination matrx to original matrix.
//o(mn) in time, o(m+n) in space solution is tricky. Allocate two array "row" and "column" to record the rows and columns that should be filled with 0.
//And do it in original matrix.
//o(mn) in time, o(1) in space is what this problem what's.
//First, we find the first 0 cell in the matrix. (If no 0 cell is found, just return the original matrix, all works are done.)
//Second, since we record the row number and column number of the first 0 cell. We know this row and column should be filled with 0
//in the result matrix. With the help of variable "row" and "column", we can use this row array and column array to serve as
//the "row" array and "column" array in o(mn) in time, o(m+n) in space algorithm.
//To be more specific, if is the first cell we found that is 0. we use row [] to record which column should be filled with 0
//and column [] to record which row should be filled with 0.
if(matrix.empty()){
return ;
}
size_t height = matrix.size();
size_t width = matrix.front().size();
//find the first 0 cell
int row = -1;
int column = -1;
for(size_t i = 0; i < height; i++){
for(size_t j = 0; j < width; j++){
if(matrix[i][j] == 0){
row = i;
column = j;
break;
}
}
if(row != -1){
break;
}
}
//no 0 cells found
if(row == -1){
return ;
}
//mark all 0 cells
for(size_t i = 0; i < height; i++){
for(size_t j = 0; j < width; j++){
if(matrix[i][j] == 0){
matrix[row][j] = 0;
matrix[i][column] = 0;
}
}
}
//fill corresponding cells with 0
for(size_t i = 0; i < height; i++){
if(i == row) continue;
if(matrix[i][column] == 0){
for(size_t j = 0; j < width; j++){
matrix[i][j] = 0;
}
}
}
for(size_t j = 0; j < width; j++){
if(j == column) continue;
if(matrix[row][j] == 0){
for(size_t i = 0; i < height; i++){
matrix[i][j] = 0;
}
}
}
//fill row,column
for(size_t i = 0; i < height; i++){
matrix[i][column] = 0;
}
for(size_t j = 0; j < width; j++){
matrix[row][j] = 0;
}
}
};``` This site uses Akismet to reduce spam. Learn how your comment data is processed.