My c++ O(mn) constant space solution


  • -2
    L

    No idea why all votes are down, one possible reason may be the 5 nested 'for' loops looks not like O(mn), but if you check it carefully, you will find out it is O(mn) indeed.

    'r' is row index, 'c' is column index, 'z' is the first row which has a zero, 'z' row is used to store columns which need to set zeroes.

    class Solution {
    public:
        void setZeroes( vector<vector<int> > &m )
        {
            for( int r = 0; r < m.size(); ++r )
            {
                vector<int>& z = m[r];
                for( int c = 0; c < z.size(); ++c )
                {
                    if( z[c] != 0 )
                        continue;
                    for( c = 0; c < z.size(); ++c ) // found 'z'
                        z[c] = (z[c] == 0);// set 'zero' columns to 1, other columns to 0
                    for( ++r; r < m.size(); ++r )
                    {
                        vector<int>& a = m[r];
                        for( c = 0; c < a.size(); ++c )
                        {
                            if( a[c] != 0 )
                                continue;
                            for( c = 0; c < a.size(); ++c )
                            {
                                a[c] = (a[c] == 0);// set 'zero' columns to 1, other columns to 0
                                z[c] += a[c]; // update 'z'
                            }
                            break;
                        }
                    }
                    for( c = 0; c < z.size(); ++c )
                        if( z[c] != 0 ) // not zero means this column has zeroes
                            for( r = 0; r < m.size(); ++r )
                                m[r][c] = 0;
                    return; // all done, return here
                }
            }
        }
    };

  • -2
    Q

    oh it's O(n) space not constant


  • 0
    L

    may I know where is the O(n) from? could you please check carefully again?


  • 0

    Yes, it's constant. Only two references to m[r] are introduced, 8 bytes in total. However, this code is hard to read and the time complexity is also hard to know.


Log in to reply
 

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