Coding Interview Question | Max size square submatrix with all 1s | Dynamic Programming

[@prashantgiri1285]

Can I get a recursive approach?

[@ashpreetsinghanand7260]

class Solution {
public:
int solve(vector &matrix, int i, int j, int &maxans, vector &dp){
if(i>=matrix.size() || j>=matrix[0].size()){
return 0;
}
if(dp[i][j]!=-1){
maxans = max(maxans, dp[i][j]*dp[i][j]);
return dp[i][j];
}
int diagonal = solve(matrix, i+1, j+1, maxans, dp);
int right = solve(matrix, i, j+1, maxans, dp);
int down = solve(matrix, i+1, j, maxans, dp);
if(matrix[i][j]=='1'){
int ans = 1 + min(diagonal, min(right, down));
maxans = max(maxans, ans*ans);
return dp[i][j] = ans;
}
else{
return dp[i][j] = 0;
}
}
int maximalSquare(vector& matrix) {
int a = matrix.size();
int b = matrix[0].size();
int maxans=0;
vector dp(a+1, vector(b+1, -1));
solve(matrix, 0, 0, maxans, dp);
return maxans;
}
};

[@sarcastic5561]

best the way u just make us understand by dry running the crux of the questions its all what we need for any questions thankyou !!

[@AR-scorp]

I really like your Dynamic Programming series. Helped me understand the algos, and without looking at your code, I was able to write the code myself, even with space optimization by using two rows.
Thanks for the videos.

[@KeertiPurswani]

That is awesome! 😇😇

[@ChristForAll-143]

Hope i would have a girl friend like you, very good explanation
Thank you

[@55_jyotirmaykar30]

Excellent video ma'am. You are way more greater than I am capable of admiring.🙏🙏🙏🙏

[@suvai_kitchen]

Excellent video. at least i found a video who explains the intuition and logic of how solution works. Other videos just jump to solution and make us accept that.
But what made you to think that the side of every square formed must be stored in another dp matrix? What brought you this thought?

[@aniketpathak6623]

Thanks for such clear explanation of the Algorithm. Please do continue this series of DP. 😊

[@KeertiPurswani]

Thanks Aniket. Going to continue this series for sure :)

[@laxman1225]

Thanks for the wonderful explanation.
How to come up with these ideas other than practice?

[@makeupby.ananya]

How would we find which element of the dp table is our answer for the entire matrix? Like how would we get the answer as 3?

[@manojjain3501]

I liked as you It mean a lot to you. :) . Excellent explanation.

[@kannanparamasivam5331]

Simple and clear explanation. Appreciate your effort!!!

[@KeertiPurswani]

Thank you 😊 😊

[@_YaelRobert]

Thanks Keerti for the good explanations! Your efforts to help us in understanding DP are highly appreciated! Thanks a lot :)
Your videos are getting better than before. Keep it up!!

[@KeertiPurswani]

Thank you so much Yael :) means a lot!

[@_YaelRobert]

@@KeertiPurswani Yup!!

[@rapakavineethkumar5429]

Excellent video, I solved this question before but never thought of this solution. I am watching all of your videos now.

[@vibhu613]

great video ------tonnes of love didi

[@yawar110]

what if we want to find the max sub metrics with all 0s instead?

[@AmanSingh-pq4rf]

Great explanation

[@sanchitmehra1079]

Very nice explanation :)

[@ashutoshjadhav]

Nicely explained ^_^

[@KeertiPurswani]

Thanks Ashutosh :)

[@devprakash5320]

Naice solution

[@arnobchowdhury9641]

Thanks a lot. Liked and Subscribed right when you said it means a lot to you.

[@KeertiPurswani]

Thank you so much. It does ❤️

[@tejasghone5118]

Great explanation!! White board explanations really simplify things.

[@KeertiPurswani]

Thank you 😊😊

[@sukdebdasthakur6749]

On which CTC?

[@sakshibhalothia8770]

Can you pls tell me why you're taking minimum when we have to find maximum?

[@KeertiPurswani]

Because all the 3 values should be 1 to form a square, even if one isn't, then it won't be square so you take minimum
Please try to go through the video once more. This is exactly what I tried to explain 😅

[@sakshibhalothia8770]

@@KeertiPurswaniGot it!!!😅 Thank you so much

[@vigneshhendrix4447]

You just Nailed it !🔥 I got the logic now. Thank yu !

[@KeertiPurswani]

Thank you 😊😊

[@KurtVanBever]

Very nice presentation and explanation 👍

[@KeertiPurswani]

Thanks. Means a lot 😇😇

[@shankar7662]

Nice Explanation!!

[@KeertiPurswani]

Thank you! 😇

[@sukdebdasthakur6749]

On which company you are working? Please reply.

[@KeertiPurswani]

Presently at Intuit. You can check on LinkedIn as well :)