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

[@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! 😇😇

[@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 !!

[@rapakavineethkumar5429]

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

[@kannanparamasivam5331]

Simple and clear explanation. Appreciate your effort!!!

[@KeertiPurswani]

Thank you 😊 😊

[@55_jyotirmaykar30]

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

[@prashantgiri1285]

Can I get a recursive approach?

[@vibhu613]

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

[@AmanSingh-pq4rf]

Great explanation

[@vigneshhendrix4447]

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

[@KeertiPurswani]

Thank you 😊😊

[@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 :)

[@tejasghone5118]

Great explanation!! White board explanations really simplify things.

[@KeertiPurswani]

Thank you 😊😊

[@shankar7662]

Nice Explanation!!

[@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!!

[@sanchitmehra1079]

Very nice explanation :)

[@manojjain3501]

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

[@KurtVanBever]

Very nice presentation and explanation 👍

[@KeertiPurswani]

Thanks. Means a lot 😇😇

[@laxman1225]

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

[@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?

[@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 ❤️

[@yawar110]

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

[@ashutoshjadhav]

Nicely explained ^_^

[@KeertiPurswani]

Thanks Ashutosh :)

[@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?

[@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; } };

[@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

[@ChristForAll-143]

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

[@sukdebdasthakur6749]

On which company you are working? Please reply.

[@KeertiPurswani]

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

[@xendu-d9v]

thanks