Maximal square | Dynamic programming | Leetcode #221 | Largest Square Submatrix of all 1's

Space Complexity: O(1)

int maxSquare(int n, int m, vector<vector<int>> mat){
// code here
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
ans=max(ans,mat[i][j]);
}
if(ans==1)
{
break;
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{ if(mat[i][j]==1){
int x=min(min(mat[i-1][j],mat[i][j-1]),mat[i-1][j-1]);
ans=max(ans,x+1);
mat[i][j]=x+1;
}
}
}
return ans;
}

Nice Explanation 😃

I mam I want talk with your about my features opportunity where can connect with you

The intuition behind this algo is that we are checking for all possible squares ending at the given index.
So, we are using the results of maximum sized squares ending at 3 adjacent indexes and using that information to find out the max possible solution at current index.

thankyou so much worth watching!!!!

thank you!

inside if( i = = 0 || j = = 0) you are doing unnecessary work you can leave it as it is , nice explanation overall 🙏thank you

Thank you so much for this approach ... this is really easy

Can we solve problems by filling dp from last cell to first

Great explanation! This helped a bunch!

please add the link as well and ur playlists are best way to revise and the way you explain gives me confidence to speak in interviews ..
Thanks a lot for amazing content

thanks a lot didi!

greatt explanation!

nice work alisha

very nice explaination

The way you are conveying the intuition part of the solution creates the difference.
Nice choice of questions btw.

thanks mam

Ufff didi one of the best place and you just explained the code in really easy way, I saw everyone's video but they just copy pasting the solution ❤❤😊

Nice explanation Indeed!