LeetCode Q73: Set Matrix Zeros

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

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?

Solution:

Use first row and column to save rows and cols having zeros. But need to check whether the first row and first column initially containing zeros. When filling the matrix, starting from the second row and second column. When finish, back to fill the first row and the first column if they initially contain any zero.

	class Solution {
	public:
	void setZeroes(vector<vector<int> >& matrix) {
	bool row0zero=false;
	for(int j=0; j<matrix[0].size(); j++)
	if(matrix[0][j]==0)
	row0zero=true;
	bool col0zero=false;
	for(int i=0; i<matrix.size(); i++)
	if(matrix[i][0]==0)
	col0zero=true;
	for(int i=0; i<matrix.size(); i++)
	for(int j=0; j<matrix[0].size(); j++)
	if(matrix[i][j]==0){
	matrix[0][j]=0;
	matrix[i][0]=0;
	}
	for(int j=1; j<matrix[0].size(); j++){
	if(matrix[0][j]==0){
	for(int i=1; i<matrix.size(); i++)
	matrix[i][j]=0;
	}
	}
	for(int i=1; i<matrix.size(); i++){
	if(matrix[i][0]==0){
	for(int j=1; j<matrix[0].size(); j++){
	matrix[i][j]=0;
	}
	}
	}
	if(row0zero){
	for(int j=0; j<matrix[0].size(); j++)
	matrix[0][j]=0;
	}
	if(col0zero){
	for(int i=0; i<matrix.size(); i++)
	matrix[i][0]=0;
	}
	}
	};

view raw Q73SetMatrixZeros.cpp hosted with ❤ by GitHub