C++, O(1)-space-solution


  • 0
    E
    class Solution {
    public:
    	void setZeroes(vector<vector<int> > &matrix) {
    		int m = matrix.size();
    		if (m == 0) {
    			return;
    		}
    		int n = matrix[0].size();
    		int R = -1, C = -1;			// to store the 0 rows and column;
    		int i, j, k;
    		int store_found = false;
    		for (int i = 0; i < m; i++){
    			for (int j = 0; j < n; j++){ 
    				if (matrix[i][j] == 0 && i != R && j != C) {
    					if (!store_found) {
    						R = i;
    						C = j;
    						store_found = true;
    						for (k = 0; k < n; k++) {			// mark the R-row
    							if (matrix[R][k] == 0) {
    								matrix[R][k] = -1;
    							}
    							else {
    								matrix[R][k] = 0;
    							}
    						}
    						for (k = 0; k < m; k++) {			// mark the C-clolumn
    							if (k == R) {
    								continue;
    							}
    							if (matrix[k][C] == 0 && k != R) {
    								matrix[k][C] = -1;
    							}
    							else {
    								matrix[k][C] = 0;
    							}
    						}
    					}
    					else {
    						matrix[i][C] = -1;
    						matrix[R][j] = -1;
    					}
    				}
    			}
    		}
    
            if (!store_found){
    			return;
    		}
    
    		for (i = 0; i < m; i++){				// set marked row to be zero
    			if (matrix[i][C] == -1) {
    				for (k = 0; k < n; k++) {
    					if (i == R || k == C) {
    						continue;
    					}
    					matrix[i][k] = 0;
    				}
    			}
    		}
    		
    		for (j = 0; j < n; j++){				// set marked column to be zero
    			if (matrix[R][j] == -1) {
    				for (k = 0; k < m; k++) {
    					if (j == C || k == R) {
    						continue;
    					}
    					matrix[k][j] = 0;
    				}
    			}
    		}
    
    		for (k = 0; k < n;k++){					// set the store row and column to be zero
    			matrix[R][k] = 0;
    		}
    		for (k = 0; k < m; k++){
    			matrix[k][C] = 0;
    		}
    	}
    };

  • 0
    S

    What's the run-time like? I took a similar approach (show below), run-time is pretty horrible.

    class Solution {
    public:
       // Store the rows, columns that are to be zeroed out in the first column, row respectively.
       // Store whether the first row and column contained zero in two additional boolean variables.
       // O(1) space solution
    
        void setZeroes(vector<vector<int>>& matrix) {
            int m = matrix.size();
            
            if(m == 0)
            {
                return;
            }
            
            int n = matrix[0].size();
            
            if(n == 0)
            {
                return;
            }
            
            bool col_has_zero = false;
            bool row_has_zero = false;
            
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(matrix[i][j] == 0)
                    {
                        if(i == 0)
                        {
                            row_has_zero = true;
                        }
                        
                        if(j == 0)
                        {
                            col_has_zero = true;
                        }
                        
                        matrix[0][j] = 0;
                        matrix[i][0] = 0;
                    }
                }
            }
            
            for(int i = 1; i < m; i++)
            {
                if(matrix[i][0] == 0)
                {
                    for(int j = 1; j < n; j++)
                    {
                        matrix[i][j] = 0;
                    }
                }
                else
                {
                    for(int j = 1; j < n; j++)
                    {
                        if(matrix[0][j] == 0)
                        {
                            matrix[i][j] = 0;
                        }
                    }
                }
            }
            
            if(row_has_zero)
            {
                for(int j = 0; j < n; j++)
                {
                    matrix[0][j] = 0;
                }
            }
            
            if(col_has_zero)
            {
                for(int i = 0; i < m; i++)
                {
                    matrix[i][0] = 0;
                }
            }
            return;
        }
    };

  • 0
    H

    the elements is non-negative?


  • 0
    V

    I don't see that specified in the question. I also had a similar idea, but I didnt make the assumption that -1 is not among the input values:-

    class Solution {
         public:
         void setZeroes(vector<vector<int>>& matrix) {
              int m = matrix.size();//2
              if(m == 0)return;
              int n = matrix[0].size();//6
              int store_row = -1;
             int store_col = -1;
             for(int i = 0;i < m;i++) {
                 for(int j = 0;j < n;j++) {
                     if(matrix[i][j] == 0) {
                          if(store_row == -1) {
                               store_row = i;//0
                               store_col = j;//2
                           }
                           else {
                                matrix[store_row][j] = 0;//matrix[0][5] = 0
                                matrix[i][store_col] = 0;//matrix[1][2] = 0
                            }
                      }
                }
        }
        if(store_row == -1) return;
        for(int j = 0;j < n;j++) {
            if(matrix[store_row][j] == 0 && j != store_col) fill_col_with_zeroes(matrix, j);
        }
        for(int i = 0;i < m;i++) {
            if(matrix[i][store_col] == 0 && i != store_row) fill_row_with_zeroes(matrix, i);
        }
        fill_row_with_zeroes(matrix, store_row);
        fill_col_with_zeroes(matrix, store_col);
    }
    
    void fill_row_with_zeroes(vector<vector<int> >& v, int r) {
        for(int i = 0;i < v[0].size();i++) {
            v[r][i] = 0;   
        }
    }
    
    void fill_col_with_zeroes(vector<vector<int> >& v, int c) {
        for(int i = 0;i < v.size();i++) {
            v[i][c] = 0;
        }
        
    } 
    

    };


Log in to reply
 

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