My solution with time complexity O(M*N) got TLE. But the solution with O(M+N) auxiliary space and O(M*N) time complexity was accepted

My solution:

void setzero(int m,int n,vector<vector<int> > &A)
{
    for(int i=0;i<A[0].size();i++)
        if(A[m][i]==1)
            A[m][i]=-1;
            
    for(int i=0;i<A.size();i++)
    {
        //cout<<A[i][n]<<" ";
        if(A[i][n]==1)
            A[i][n]=-1;
        //cout<<A[i][n]<<"\n";
    }
}

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

Got TLE, even though my time complexity is O(M*N) i.e same as another accepted solution.

This isn’t the correct time complexity, in the worst case (the entire matrix was with zeros) you iterate for each cell over its entire row and col.

So your algorithm time complexity is really O(mn^2+nm^2)

Click here to start solving coding interview questions