O(m*n) time complexity and O(n) Space Complexity - Space efficient


#1
int m = A.size();   
if(m==0) return 0;     //No Matrix case
int n = A[0].size();

vector<int>dp1(n,0);    
vector<int>dp(n);

int max = 0;
for(int i=0; i<n; i++)
{
    dp[i]=A[0][i];
    // 1 element square
     if(A[0][1]==1) max = 1;
}


for(int i=1; i<m; i++)
{
    for(int j=0; j<n; j++)
    {
        if(j==0) dp1[j] = A[i][j];
        else if(A[i][j]==1) 
        {
        dp1[j] = min(dp1[j-1],min( dp[j], dp[j-1])) + 1;
           
        }
         if(dp1[j]>max) max = dp1[j];
    }
     for(int k=0; k<n; k++){
       dp[k] = dp1[k];
        dp1[k] = 0;
    }
}
   
    return pow(max,2);
}