Constant space, O(mn) C++ solution.


  • 0
    L

    Basically uses the first row and column to store whether to zero out the row or column respectively.

    class Solution {
    public:
        void setZeroes(vector<vector<int> > &matrix) {
            if(!matrix.size())return;
            int i,j;
            const int rows=matrix.size(),cols=matrix[0].size();
            bool firstrowzero=false, firstcolzero=false;
            
            for(i=0;i<rows;i++)
                for(j=0;j<cols;j++)
                    if(!matrix[i][j]){
                        matrix[i][0]=matrix[0][j]=0;
                        firstrowzero=firstrowzero||i==0;
                        firstcolzero=firstcolzero||j==0;
                    }
            for(i=1;i<rows;i++)
                if(!matrix[i][0]) 
                    matrix[i].assign(cols,0);
            for(i=1;i<cols;i++)
                if(!matrix[0][i]) {
                    for(j=0;j<rows;j++)
                        matrix[j][i]=0;
                }
            if(firstrowzero)
                matrix[0].assign(cols,0);
            if(firstcolzero)
                for(j=0;j<rows;j++)
                    matrix[j][0]=0;
        }
    };

  • 0
    T
    This post is deleted!

  • 0
    W

    The first row and column will change during the following step?
    if(!matrix[i][j]){
    matrix[i][0]=matrix[0][j]=0;
    firstrowzero=firstrowzero||i==0;
    firstcolzero=firstcolzero||j==0;
    }


  • 0
    L

    the trick is to use the first row and column to indicate which rows and columns to erase later on.


Log in to reply
 

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