Space optimized solution with complete discription and code, c++


  • 2
    R

    This method uses the first row and first column of the input matrix as an auxiliary arrays to indicate which row and which column is set to 0.

    So what we do is: first take care of first row and column and store the info about these two in two flag variables rFlag and cFlag.

    Here is the Algorithm,
    1) Scan the first row and set a variable rFlag to indicate whether we need to set all 1s in first row or not.

    2) Scan the first column and set a variable cFlag to indicate whether we need to set all 1s in first column or not.

    3) Use first row and first column as the auxiliary arrays , consider the matrix as submatrix starting from second row and second column.

    5) If element at position (i,j) is zero set position (0,j) as 0 and set position (i,0) as 0.

    6) Traverse the matrix excluding first row and first column. If either (0,j) or (i,0) is 0 then set position (i,j) as 0.

    1. Finally, using rFlag and cFlag, update first row and first column if needed.

    Time Complexity: O(ROWCOL)*

    Auxiliary Space: O(1)

    Here is the code for above idea.

    Thank you

    void setZeroes(vector<vector<int>>& matrix) {
        int row = matrix.size();
        if( row == 0) return;
        int col = matrix[0].size();
        int rFlag=0,cFlag=0;
        
        for(int j=0 ; j<col ; j++) if(matrix[0][j]==0) rFlag=1;
        for(int j=0 ; j<row ; j++) if(matrix[j][0]==0) cFlag=1;
        
        
        for(int i=1 ; i<row ; i++){
            for( int j=1 ; j<col ; j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        
        for(int i=1 ; i<row ; i++){
            for( int j=1 ; j<col ;j++){
                if(matrix[i][0]==0 || matrix[0][j]==0) matrix[i][j]=0;
            }
        }
        
        if(rFlag)for(int i=0 ; i<col ; i++) matrix[0][i]=0;
        if(cFlag)for(int i=0 ; i<row ; i++) matrix[i][0]=0;
    }

Log in to reply
 

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