Is there any Constant Space Solution With just One Pass?


  • 0
    C

    I used 2 arrays to store row and column numbers. Then loop through the matrix and remember 0's row/column indexes. Finally loop through matrix again to fill in 0. The space complexity is O(row + column) and time complexity is O(2*n), n = size of matrix.

    I do not post my solution since it is similar to other people. Does anyone try to solve this problem via constant space and O(n) time? Even though I doubt if such solution can be found, it is high possible to be asked to optimize this solution in an interview, I guess.


  • 0
    J

    I think this is exactly what you are looking for. My solution is One Pass with O(1) space.
    I had a hard time to explain how it works to the friend of mine, it really does just one traversal and sets each cell to 0 only one time, except when it set entire row, which was marked as "set to 0s".

    void setZeroes(vector<vector<int> > &matrix) {
            
            if (matrix.empty()) return;
            int M = matrix.size();
            int N = matrix[0].size();
            
            int row=-1;
            bool markThisRow=false;
            
            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    if(matrix[i][j] == 0){
                        // for each 0-cell set all cells on top of it to 0s (this will be done only once, if there were no 0s in this column before)
                        for(int k=i-1; k>=0; k--)           { matrix[k][j] = 0; }
                        
                        markThisRow=true; // say "this Row need to be set to 0s"
                    }else{
                        // set current cell to 0 only if cell on top of it is 0
                        if(i>0 && (matrix[i-1][j] == 0))    { matrix[i][j] = 0; }
                    }
                }
                
                // if "previous" Row was marked - set that row to 0s
                if(markThisRow) {
                    if(row >= 0) { setRow(matrix,row); }
                    row=i; // set index of the current Row to set it later.
                    markThisRow=false;
                }
            }
            
            // here we go, after all row has index of the latest row marked, so set all cell of it to 0s
            if(row >=0 ) setRow(matrix, row);        
        }
        
        void setRow(vector<vector<int> > &m, int i){
            for(int j=0; j<m[i].size(); j++)    m[i][j]=0;
        }

  • 0
    W

    I think I can understand your hard time in explaining to your friend about it. Cool solution!


  • 0
    J

    I think your solution has problem.
    After you set the current row as all Zero. When you go to the next row, it will check whether matrix[i-1][j]==0. But actually, even matrix[i-1][j]==0, it doesn't means matrix[i-1][j] is originally zero, it may be set zero after one zero found in i-1 row.
    Consider about this.
    You can try this test case:[[0,0,0,5],[4,3,1,4],[0,1,1,4],[1,2,1,3],[0,0,1,1]]


  • 0
    J

    yeah, exactly where the friend of mine could not get it. Take a carreful look to the condition "if(markThisRow) ...", there setRow is called with index "row", not i. This time row has index of previous row which had to be set to 0s.


Log in to reply
 

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