DP C++ solution :)

interview-questions
Tags: #<Tag:0x00007f24280cba40>

#1

vector<vector>check(A.size()+1,vector(A[0].size()+1));
for(int j=0;j<check[0].size();j++){
check[check.size()-1][j]=0;
}
for(int i=0;i<check.size();i++){
check[i][check[0].size()-1]=0;
}
int max1=0;
for(int i=check.size()-2;i>=0;i–){
for(int j=check[0].size()-2;j>=0;j–){
if(A[i][j]==0){
check[i][j]=0;
}
else{
check[i][j]=min(check[i][j+1],min(check[i+1][j],check[i+1][j+1]))+1;
if(check[i][j]>max1){
max1=check[i][j];
}
}
}
}
return max1*max1;