Is there a better constant space solution?


  • 10
    G

    My solution is kind of hackish - accpeted. So, I want to know if there is a better constant space solution?

    I traverse the matrix and if I find a zero, I replace all the elements, except the 0 elements, of the corresponding row and column with -1. Finally I make all the -1 to 0.

    This algorithm would fail if the matrix has -1s.

        void setZeroes(vector<vector<int> > &matrix) {
        
        int i,j,k,m,n;
        
        m = matrix.size();
        n = matrix[0].size();
        
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                if(matrix[i][j]==0)
                {
                    for(k=0;k<n;k++)
                        if(matrix[i][k]!=0)
                            matrix[i][k] = -1;
                    for(k=0;k<m;k++)
                        if(matrix[k][j]!=0)
                            matrix[k][j] = -1;
                }
        
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                if(matrix[i][j]==-1)
                   matrix[i][j]=0; 
    }

  • 0
    I

    If all elements are -1 (no 0), your solution will set all of them to 0.


  • 0
    G

    Yes, I agree... that is the reason why I called it hachisk and want to know if there is a better solution.


  • 136
    S

    Here is n00tc0d3r's answer from old discuss. Thanks to n00tc0d3r.

    The basic idea is to use the first row and column to store the information. Then we need to know whether or not to set the first row and column to zeroes. So, we use two boolean to store that information.

    public void setZeroes(int[][] matrix) {
        int rownum = matrix.length;
        if (rownum == 0)  return;
        int colnum = matrix[0].length;
        if (colnum == 0)  return;
    
        boolean hasZeroFirstRow = false, hasZeroFirstColumn = false;
    
        // Does first row have zero?
        for (int j = 0; j < colnum; ++j) {
            if (matrix[0][j] == 0) {
                hasZeroFirstRow = true;
                break;
            }
        }
    
        // Does first column have zero?
        for (int i = 0; i < rownum; ++i) {
            if (matrix[i][0] == 0) {
                hasZeroFirstColumn = true;
                break;
            }
        }
    
        // find zeroes and store the info in first row and column
        for (int i = 1; i < matrix.length; ++i) {
            for (int j = 1; j < matrix[0].length; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
    
        // set zeroes except the first row and column
        for (int i = 1; i < matrix.length; ++i) {
            for (int j = 1; j < matrix[0].length; ++j) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)  matrix[i][j] = 0;
            }
        }
    
        // set zeroes for first row and column if needed
        if (hasZeroFirstRow) {
            for (int j = 0; j < colnum; ++j) {
                matrix[0][j] = 0;
            }
        }
        if (hasZeroFirstColumn) {
            for (int i = 0; i < rownum; ++i) {
                matrix[i][0] = 0;
            }
        }
    }

  • 0
    L

    Your method will change the elements in row 0 and column 0 if they did not need to be zero. Is there any other method without changing the numbers not needed to be changed?


  • 0
    S

    @Liangjun No, this method does NOT change the "elements not needed to be changed". If an element A in row 0 or column 0 is set to 0 at some point, it means another element B which lies on the same row or column as A must also be zero. In that case, A really need be set to 0 in the desired output after all.


  • 0
    D

    We actually don't need hasZeroFirstColumn = false; and don't need to traverse first column before we start, we only need special treatment for first row. Since whether first column needs to be zero filled could be determined by matrix[0][i] (which i is 0) as other normal column.
    Of course at the end we have to set zero for first column individually like the post did.


  • 0
    W

    why not directly set all the element to be zero ...


  • 0
    I

    Nice! Using the matrix to store the information...


  • 0
    P

    IMHO, this sacrifices the time complexity too much, especially when many of the elements are 0.


  • 0
    X

    I use an array to keep the information which row and column should be set to zero.
    The size of array is max(m,n).
    Here is my code:

    void setZeroes(vector<vector<int> > &matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        
        int max = row>col?row:col;
        
        int A[max];
        // set the element of A to zero;
        // A[i]=0:the initial valule;
        // A[i]=1:the row shoule be set to zero;
        // A[i]=2:the column shoule be set to zero;
        // A[i]=3:both the row and column should be set to zero;
        // Thus the extra space used : O(max(m,n))
        for(int k=0;k<max;k++)
            A[k]=0;
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
            {
                if(matrix[i][j]==0)
                {
                    if(A[i]==0||A[i]==1)
                        A[i] = 1;
                    if(A[i]==2)
                        A[i] = 3;
                        
                    if(A[j]==0 ||A[j]==2)
                        A[j] = 2;
                    if(A[j]==1)
                        A[j] = 3;
                }
            }
            
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
            {
                if(A[i]==1||A[i]==3||A[j]==2||A[j]==3)
                    matrix[i][j] = 0;
            }
    }

  • 0
    M

    As your array is size max(m,n), it has a linear space complexity, not constant, as this question is asking for.


  • 0
    S

    because it will overwrite those entries whose initial value is zero.


  • 1
    H

    My solution is find the first zero element, let's say, A[i][j], then I set the zero element to 1, and non-zero element to 0 in ith row and jth column. the I traverse all the remains row and use ith row and jth column to record.

    class Solution {
    public:
        void setZeroes(vector<vector<int> > &matrix) {
            int i = -1, j = -1;
            for(int m = 0; m < matrix.size(); m ++)
                for(int n = 0; n < matrix[m].size(); n ++)
                    if(matrix[m][n] == 0)
                    {
                        i = m;
                        j = n;
                        m = matrix.size();
                        break;
                    }
            if(i == -1)return;
            for(int k = 0; k < matrix.size(); k ++)
                if(matrix[k][j])
                    matrix[k][j] = 0;  
                else
                    matrix[k][j] = 1;
            for(int k = 0; k < matrix[i].size(); k ++)
                if(matrix[i][k])
                    matrix[i][k] = 0;
                else
                    matrix[i][k] = 1;
            for(int m = i + 1; m < matrix.size(); m ++)
                for(int n = 0; n < matrix[m].size(); n ++)
                    if(matrix[m][n] == 0 && n != j)
                    {
                        matrix[i][n] = 1;
                        matrix[m][j] = 1;
                    }
            for(int m = i + 1; m < matrix.size(); m ++)
                if(matrix[m][j] == 1)
                    for(int n = 0; n < matrix[m].size(); n ++)
                        matrix[m][n] = 0;
            for(int n = 0; n < matrix[i].size(); n ++)
                if(matrix[i][n] == 1)
                    for(int m = 0; m < matrix.size(); m ++)
                        matrix[m][n] = 0;
        }
    };

  • 21
    R

    My solution has the similar idea as n00tc0d3r's. But I use a different way to check whether the first row or column has zeros

    void setZeroes(vector<vector<int> > &matrix) {
        if (matrix.empty()) return;
        int m = matrix.size();
        int n = matrix[0].size();
        bool row = false, col = false;
        
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    if (i == 0) row = true;
                    if (j == 0) col = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j) 
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
                    
        if(row)  for (int j = 0; j < n; ++j) matrix[0][j] = 0;
        if(col)  for (int i = 0; i < m; ++i) matrix[i][0] = 0;    
    }

  • 0
    H
    This post is deleted!

  • 0
    L

    I have to admit, this is really awesome.


  • 0

    This is an awesome solution. Thanks!


  • 0
    F

    nice algorithm! use the space of the input to store data, really nice!


  • 0
    N
    This post is deleted!

Log in to reply
 

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