LeetCode #73

# Description:

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?

## Example:

``````Note
``````

# Idea:

time: O(mn), Space: O(1)

# Code:

``````class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if(matrix.empty()) return;

int m=matrix.size();
int n=matrix[0].size();
bool row_zero=false;
bool column_zero=false;

for(int i=0; i<m; ++i){
if(matrix[i][0]==0){
column_zero=true;
break;
}
}
for(int j=0; j<n; ++j){
if(matrix[0][j]==0){
row_zero=true;
break;
}
}

for(int i=1; i<m; ++i){
for(int j=1; j<n; ++j){
if(matrix[i][j]==0){
matrix[i][0]=0;
matrix[0][j]=0;
}
}
}

for(int i=1; i<m; ++i){
for(int j=1; j<n; ++j){
if(matrix[i][0]==0 || matrix[0][j]==0){
matrix[i][j]=0;
}
}

}

if(row_zero){
for(int j=0; j<n; ++j){
matrix[0][j]=0;
}
}
if(column_zero){
for(int i=0; i<m; ++i){
matrix[i][0]=0;
}
}

}
};
``````