Maximal square | Dynamic programming | Leetcode

This video explains a very important dynamic programming question which is the maximal square problem from leetcode #221. This has frequently been asked in interviews. In this problem, you are required to find the largest square formed by a binary matrix and the square should have all 1s in it. We need to return the area of the largest square matrix as our answer. This problem can be solved by depth first search, recursion and backtracking but they will consume a lot of time and so i have shown the intuitive approach to solve this problem by dynamic programming. I have shown the solution using proper examples to develop intuition for DP. CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...

[@quirkyquester]

"im not sure if you can understand this" and "I hope you are understanding this" haha, love these two quotes haha lol

[@techdose4u]

😅

[@pl5778]

this is probably the best visual explanation i've seen thus far. This is really excellent, the ability to break it down with such simplicity. Subscribed.

[@techdose4u]

Thanks :)

[@Corona0715]

Unbelievable 😌😌
Subscribed :)

[@charlesbickham6604]

Man I dont how you get answers like this! Been doing the leetcode 30 day challenge with you. Love your way of thinking and understanding! Would love for you to do a video of when to use different approaches like backtracking, sliding window etc!

[@techdose4u]

I will do it soon bro....

[@alperozdamar517]

Marvelous solution! I love DP programming and your thought process. Thank you.

[@techdose4u]

Welcome :)

[@quirkyquester]

amazing explanation, thank you! I love how you walk us through your thought process and assume that we don't know what you are talking about.

[@techdose4u]

Yep I can't assume everyone to understand me completely 😅

[@ploratran]

Thank you this is the easiest explanation I've found so far on the internet for this problem.

[@mondayemmanuel191]

You've been a great help in my learning of DSA. Thank you.

[@techdose4u]

Welcome :)

[@rishabhpathak9916]

The way u explain with examples and all sorts of intutions, helps a lot to understand complex algorithms and codes. Yhank you so much

[@techdose4u]

Thanks bro :)

[@parthshah6343]

I have seen your previous videos too, you are one of the best when it comes to explaining solutions!

[@techdose4u]

Thanks :)

[@amitavamozumder73]

this was so simple, but finding a rectangle was so complicated, we literally converted that to a histogram for each row and calculated that. wish there was a simple dp like this for that problem.

[@hanieharabzadeh4185]

This channel deserves more subscription. You explained very well . Thanks a lot!

[@techdose4u]

Welcome :)

[@sumitanglekar6309]

The Best Explanation of DP. Made it look so easy at the end !!

[@techdose4u]

Thanks :)

[@khan.mansoor]

So underrated but such a useful video with very clear explanation. I was able to solve a related problem after watching the video halfway. Thank you so much.

[@techdose4u]

Welcome :)

[@dragonindian1]

You are doing awesome job, i have refered other video where people just memorize and repeat, you understand and explain things. Very helpful. Keep doing the good work.

[@techdose4u]

Thanks bro :)

[@robinofautumn99]

Thankyou for such an amazing video!!

[@ankitkumaryadav562]

Nice Explanation you are doing great job.................:)

[@SujeetKumar-hh5jz]

Even beginners can understand DP , the way you explain is soo good.

[@techdose4u]

Thanks

[@ronitdhingra4395]

As always...the best explanation available on youtube.....Thanks a lot surya...
TechDose, helping us learn DS and get jobs since 2019:)

[@vivekswami2182]

Love the explanation man !!

[@ankurgupta4696]

thanks a lot for explaning such a hard problem in a easy way:)

[@alokbhowmik3547]

Awesome explain bror 👍👍

[@mrinalraj7166]

Hi TechDose, Congratulations on making such a beautiful video. You always succeed in making a deeper dive into the concept behind a solution.

[@techdose4u]

Thanks :)

[@SexyAnvesha]

You simplified the problem, very well explained. thanks!!

[@techdose4u]

Welcome :)

[@nehasomani3446]

Really good explanation!! Thanks a lot!

[@amityanarayan8808]

Awesome thanks! By far a detailed explanation. Subscribed for more.

[@techdose4u]

Welcome 😄

[@kitkarson4226]

I was super confused how to solve the problem. You gave me a nice hint. Thanks.

[@techdose4u]

Welcome

[@testtest674]

hi , please could you tell me how to find the indexes where the square matrix begins ?

[@savy9554]

Amazinggg sir 🙏🏻

[@shahjaysheeldipalbhai207]

excellent explanation

[@sahilanand30]

Best explanation 🔥

[@kanishkagupta5801]

This type of approaches are far beyond our thought. How to proceed for this kinda questions?

[@evgeni-nabokov]

Practice, practice, sis... Train your sense of determining the problem is solved by applying DP (1 dimension or 2 dimensions, or even more), and then follow some formal steps: what is a sub problem, what is recurrent formula, what are the initial values, which way to fill the table where is the answer in the table.

[@techdose4u]

You will need a lot of practice to identify solution for these questions :)

[@Siva-lx9dw]

@@techdose4u how to practice??

[@toksdotdev]

@@Siva-lx9dw Solve more questions and explore different solutions to a problem.
Before solving a problem, you can try to come up with a solution (especially when your interview is far away).
Also, once you see a solution to a problem, don't just move on. Analyze why the solution works the way it, and compare it to how you were approaching the problem in the first place (even though you never arrived at the solution).
Analyze the data structures used, and question why that specific data structure was used, and if you could solve it with an alternate data structure.
In summary, analyze solutions, and ask your self why it works the way it works. Try to code the implementation (this is also one way to learn deeply why a solution works).

[@rahulreddy7484]

No words to appreciate ur xplaination.

[@techdose4u]

Thanks :)

[@aakashparmar3999]

What a great explanation!!

[@saitejam3769]

Such a great programmer and the way of explanation is very nice we want more videos like this. sir try to make videos on recursion.

[@rahulchudasama9363]

Nice explaination ...

[@techdose4u]

Thanks

[@bulb_blub]

Your videos have been helping me out a lot. Just wanted to say thanks

[@techdose4u]

Welcome :)

[@neelsoni13062]

Amzing Sir.

[@avikmallick2493]

Tech dose has become my daily dose

[@techdose4u]

❤️

[@mohammadumaidansari6617]

Clear Explanation ! 👌👨‍💻

[@techdose4u]

Thanks :)

[@shivatrivedi6964]

u r amazing.....thnku

[@francesn7715]

You make the best explanation videos for leetcode, hands down. Please make a video for #31 Next Permutation

[@techdose4u]

Thanks. I will try to make it soon :)

[@Official-tk3nc]

Great explanation brother proud to be an indian:)

[@Usurperhk]

Best explanation of the problem. Hat's OFF......

[@techdose4u]

Thanks

[@saunaknandi1814]

so talented bruhh

[@indsonusharma]

Ye pyaar nhi toh aur kya hai !
Amazing video bro 👌

[@techdose4u]

Thanks :)

[@shyamprakashm6325]

Thanking you bro ..it is very much helpful to me in the views of placement ..keep posting bro..😍😍😍😍

[@techdose4u]

Sure will keep posting :)

[@adarshagrawal5858]

Good Problem hard to think !!

[@techdose4u]

Sure is :)

[@Paunitza]

Very good explanation. Thank you!

[@techdose4u]

Welcome :)

[@biharichawal5412]

Thanks for help with this question, your explainations are really good

[@techdose4u]

Thanks 😊

[@hussainrangwala1078]

Very well explained. Thanks!!

[@techdose4u]

Welcome

[@pixlphotography5982]

can u explain why we take min from three directions??

[@TP-xt4sv]

excellent.

[@JamesHalpert8555]

Very nice explanation!!! Thank you!!

[@techdose4u]

Thanks bro :)

[@akashskumar99]

great job;
but u could have done it with just m*n dp instead of m+1*n+1 dp by hard coding top row and left column as default values of original matrix avoiding confusion

[@aviligondagowtham1153]

Sir can u tell more problems on dynamic programming concepts bcz so many placement questions asked on this basis

[@techdose4u]

I will make a separate video on common patterns in dynamic programming questions. This will help you figure out the approach more in depth.

[@ankitpaul723]

@@techdose4u Thanks! waiting for that video!

[@clairekowalsky4913]

Hi, @TECH DOSE Were you able to make this video? Sorry for pestering you, but it would be really helpful if someone could provide a link to this if he has made it.

[@techwills4619]

I had some hard time fully understanding the DP approach so I managed to come up with another way to solve it in O(Nrows * Ncols) time and O(Ncols) space. The idea is to reuse what we learned with largest rectangle of 1s in a matrix. Once we get a histogram, just look for a square with side equal to (1 + current maximum side). I may make a video of it on my channel

[@aayushpagare9366]

Amazing

[@shantanujoshi3863]

Awesome

[@prakhyat2001]

GOD Level explanation

[@sakthim7160]

Clean and clear explanation!

[@techdose4u]

Thanks :)

[@paragroy5359]

Nice explanation sir...you are doing a great job

[@techdose4u]

Thanks

[@pramodkumarramasani5327]

Great explanation

[@techdose4u]

Thanks

[@ace-xxx]

you explain every problem very nicely.......can you please make a series of important questions for placement.

[@techdose4u]

I have already told that questions which you find on interviewbits are already sorted in order of importance. I will make my own set of problems once I get my website running. But it will not be soon. So, I suggest you to start interviewbits

[@piyushdasila6129]

good explanation!!!

[@techdose4u]

Thanks

[@ankitghosh9873]

wowwwww what an explanation!!!!!!!!!

[@techdose4u]

Thanks ☺️

[@sase1017]

very good and detailed solution, thanks

[@techdose4u]

Thanks

[@rahulvutukuri9254]

please do provide lnks for JAVA solutions if possible, you are doing great job Thanks

[@SFsachin]

Lit🔥🔥 great video!

[@techdose4u]

Thanks buddy :)

[@codingwithanonymous890]

Sir how to do recursiveky

[@sagarsingh-wb8ou]

Hi , Can someone explain in first way how he is using dfs??

[@akashtyagi7182]

Crisp and clear explanation. Thanks !
All of your videos are of great help. If you would like I can contribute to Python solutions of your videos. Github repo will be a good idea.

[@techdose4u]

Nice .....I will create one....

[@rohitkumar2984]

1st row and 1st column is not necessary in dynamic 2d array. We can take a 2d dp array of same size as input and fill it's 1st row and 1 column separately by the elements same as present in input array and then we can follow the same approach as mentioned in the video to fill other rows and columns.

[@singhsaab7121]

Why we just checked dp [i-1][j-1] == 1 and not other two cells in if condition?

[@jpnr8]

awesome bro!

[@techdose4u]

Thanks

[@hoyinli7462]

great diagrams!

[@techdose4u]

Thanks

[@anshularora2073]

best explanation... thankyou

[@techdose4u]

Welcome

[@chris.w391]

Nice explain, thanks!

[@techdose4u]

Welcome :)

[@adityarathi3420]

Thanks sir :-)

[@techdose4u]

Welcome

[@backslash8874]

Awesome explanation.
I don't know how can anyone dislike it.

[@techdose4u]

Thanks :)

[@financewithsom485]

Mind blowing approch

[@techdose4u]

Thanks :)

[@MrDheeraj14]

very well explained!

[@techdose4u]

Thanks

[@akhilak2084]

Now I knew when I saw the question that it's got something to do with DP. But I froze at the thought of coding a DP solution. What do you recommend to practice in/read for getting more confident?

[@techdose4u]

Both reading and practice will help. But the imp thing is to notice dp patterns, where to use and where not to. Observing is important.

[@akhilak2084]

Thank you sir 😊

[@techdose4u]

Welcome :)

[@bhavyanayyer3391]

sir pls check this solution not working in interviewbit

[@yitingg7942]

Wow, thank you so much Sir ! I can understand it lol..

[@techdose4u]

Welcome :)

[@yitingg7942]

@@techdose4u I found out that for a problem if I watched your video, I can remember the solution for a Longgg time, if watch other's video I will forget the solution the next day. 😂

[@techdose4u]

@@yitingg7942 keep watching our videos ❤️

[@designandcraft]

very helpful video...

[@techdose4u]

🤣

[@spetsnaz_2]

@@techdose4u 😂😂

[@harshalgarg1149]

Thanks.

[@techdose4u]

Welcome

[@one_minute_iitian_ai]

Hi Sir,
Your explanation is crystal clear. 😊
Can you please tell me the name of Recording application?
I tried to Google but didn't find any recorder as good as this.
Reply reply 😊

[@techdose4u]

Camtasia

[@madhvansharma5917]

Hi, I don't think we needed a dp matrix of size [n+1]*[n+1]. I think dp[n][n] would have worked. BTW love your videos :)

[@techdose4u]

Take whatever works :)

[@spetsnaz_2]

I tried solving this problem using DFS and got TLE on last 3 test cases on LEETCODE as you said, but got accepted in GEEKSFORGEEKS 😜

[@techdose4u]

😅

[@crimsoncad3230]

How did you solve using DFS???

[@spetsnaz_2]

@@crimsoncad3230 I just checked if encountered 1, then dfs from that location and incresed the count diagonally and check whether all are 1s in that square
here is my code
bool isSafe(int i, int j, vector grid){
if(i= grid.size() or j= grid[i].size())
return 0;
return 1;
}
int dfs(int i, int j, int count, vector grid){
//check diagonal right is 1 or not
if(!isSafe(i+1, j+1, grid)){
return count*count;
}
//then check for max size of square formed
for(int k=0; k ans ? curr : ans;
}
}
}
return ans;
}

[@aayushpagare9366]

should have memoized then

[@tanishqgupta1071]

Nice explanation 🙂

[@techdose4u]

Thanks :)

[@rajesh1341]

Thank you. your video helped me solved the problem. But I feel I am lacking so much more. Can anyone please tell me how do I improve dynamic programming problems? Can you recommend any resources? These DP problems are lowering my confidence day by day.

[@techdose4u]

Don't be down. It's just a matter a time when you pick them. DP is always tricky 😅

[@rajesh1341]

@@techdose4u Thanks for kind words :) I started leetcode with "30 days challenge" only. out of 26 problems I was able to solve only 16. Remaining times, I had to look for explanations and understand and submit. So I was looking for help if I need to prepare and understand something, before answering leetcode solutions.
Bytheway your explanation is so crisp than many other foreigner leetcode videos. They directly jump to code.

[@techdose4u]

I don't find meaning in explaining code. The important thing is how you thought about that process. Practice is always good. 16 is better than 15. You did well. You will only improve from here on. So don't stop. Keep practicing :)

[@oyeshpatel8791]

Which would you suggest to learn dp?

[@techdose4u]

Pardon? I think you want to know what to learn. Keep practicing dp questions. As you practice, keep searching about each and reason for a step. In this way, you will learn dp.

[@MakrandPatil17]

Why are you checking dp [i-1][j-1] == 1 in if condition ??

[@saptarshidas488]

Diagonal adjacent cell is being checked here

[@SHASHANKRUSTAGII]

dp is very beautiful

[@techdose4u]

:)

[@hritikagarwal7676]

what is the intuition behind using "min" in these elements?

[@saptarshidas488]

The idea is to check if there are occurrences of 0s in any of the past adjacent cells. Say you are currently at i = 3, j = 4 of the above example.
If you take min of past adjacent cells, and it comes out as 0 then it means that a 2×2 square matrix CANNOT be formed.
If you have min as 1 that means 3×3 matrix of 1s cannot be formed, here only a 2×2 is possible.

[@vrushabh_kulye7060]

i also solved this question by dp, it seems easy for me...still i watch your all videos to get better understanding 😄😄

[@techdose4u]

Nice :)

[@sudhamahajan2272]

what if we had to find rectangle instead of square??

[@saptarshidas488]

Well, a rectangle can be thought of as combination of 2 or more squares in the matrix. So we have to find continuous ccurrences of 2s or 3s or any higher number in a row of this DP matrix.
We may take a counter "c" initialised to the first occurrence of a number >=2 in each row. And then increment it by one as an when we find more continuous occurrences of that number in the same row. We compute the area of a possible rectangle in each row traversal and store this value in a max variable. The area can be calculated as: counter × largest

[@bitrish34]

🔥🔥

[@techdose4u]

👍

[@rajeshbammidy180]

I think we can do it like the way we solve "Largest square in a histogram"

[@rishabhshukla5719]

How?

[@rajeshbammidy180]

@@rishabhshukla5719 If you are aware of finding largest rectangle in a binary matrix you can apply the same logic(with some changes ofc)

[@Analogue-India]

Please sir, make a video on problem Game of two stacks of hackerrank

[@techdose4u]

I have added this problem in my already long todo list. Will make it as soon as I get time for sure.

[@Analogue-India]

@@techdose4u Thank you sir