Largest Square of 1's in A Matrix (Dynamic Programming)

[@pascalfragnoud2846]

You don't actually have to keep a record of the full matrix, the only line is enough. So you can make a 2 by n array, and use one line as your cache, and the other one for your computations. To select which is which: For index i == 3 for example, you'd access your computation line with (3 & 1), which gives you 1, and your cache is the other one, which you can access with ((i & 1) ^ 1) or in many other ways. This reduces space complexity down from n squared to 2*n, a huge improvement for very large matrices.

[@davidjames1684]

I would go about this differently... Since we know the input matrix is 4 rows and 5 columns, the largest square of 1s there can be is 4x4, so the only place that can be is at the upper left corner or 1 element to the right of that. As soon as we scan across the top row, we see a 0, and realize a 4x4 of 1s cannot be present. We repeat this logic with 3x3 and find it and then we are done. No need to fuss with squares of size 2x2 in this example because we are checking largest (4x4) to smallest (1x1) and stopping when we find one (in this case stopping at 3x3). More specifics about the algorithm at the 3x3 check step would be scan across until we find 3 ones in a row (literally), go back to that "home" position (the leftmost element), and scan down to see if there are 3 ones in a column. If so, now we have a 3x3 "outline" so check the remaining elements inside that (only 4 more elements to check). If all are ones, we are done. Actually an improvement of this algorithm can be to first count up the # of 1s. Since we only have 14, we know that a 4x4 square of 1s is not possible, so immediately start looking for 3x3s since there are at least 9 1s. There are likely many more algorithms that will solve this too. Probably dozens.

[@CompleteMeYT]

Good lesson. One small suggestion: we can avoid that whole if-else by simply doing cache[i][j] = (1 + min(...)) * matrix[i][j]. With that solution, we don't need to clone the entire matrix. We can start with an uninitialized matrix, copy the first row and first column, then iterate starting at 2nd row and 2nd column.

[@saplingqwason]

interesting solution. I would iterate through the matrix , adding to a temp until I see a zero-->Only run a nested loop if temp> current largest. --> Nested loop will continue until a zero or confirmation of replacing maximum. This would allow me to stop the loop "early" by comparing remaining idx positions e.g. min(endofx-currentx ,endofy-currenty) < result---> return result Another interesting way could be to sum each array and calculate maximum results backwards until you finally find one equal to its maximum square or the maximum possible == result

[@yannicbrandstetter8265]

pls give the interviewer a mic or put him closer to the cam

[@dvdh8791]

Space complexity can be reduced to O(N) by only keeping track of the previous row and the current row of the cache.

[@sarthaksrivastav3408]

Or it can be O(1) if you just modify the matrix given to you.

[@paritoshpradeep4626]

Bro I have started my journey towards DS & Algos for interview purpose just now and have solved many questions and have watched many videos by other people, but the way u explained is awesome ,keep it up and make more such videos for the community.

[@GurdeepSabarwal]

i was trying to understand this problem , and No one did explain this problem better than this guys(Iterative Approach). you are awesome IrFaN!

[@analogylibrary]

Good one but different too. Actually the idea of explaining on board like you are being interviewed earned my subscription.

[@Shini1984]

Going bottom right corner does not differ at all from top left. You can just "flip the board", meaning you can start from bottom right corner instead (I think this is what is called "bottom up solution" when you start from the end of your computational area). Same as starting with top left, when starting from bottom right you can skip bottom row and right column as they will never have a value bigger than 1. This is how I solved it when I first encountered this question on leetcode.

[@kant.shashi]

perfect way to approach a DP problem

[@kambalavijay6800]

Irfan bhai solution itna simple kaise ho sakta? What great a way to start and take this down to solution very much appreciable work Irfan bhai.

[@jakelazareth1]

Perhaps the best explanation I've seen for this problem. Thank you!

[@angelv.g.8046]

This algorithm can be improved off if you start indexes as follow i=1 , j=1, since the first row and first column never changed.

[@isingcauseimliving]

I used the same technique in my Computation Fluid Dynamics class...

[@wibbthebubblyt5174]

"mhm"

[@owaiswasim8911]

This is the best step by step approach i have found.. Thanx!!

[@ajaikumar958]

Irfan, keep posting more great videos like this. These are so valuable for many people wanting to get the thought process for solving any question.

[@zionsiton3690]

Great video and approach to answering the question for a coding interview by the way. One thing I would change based on your solution would be to start the iterators at 1 instead of zero. Not only would that save iterations (as you don't need to change the cloned values when i or j are zero, but it also removes the need to check if i or j are zero. Again, great video

[@shashanksingh99]

Dude you are one of the best thing that happened to KZbin (For Programmers atleast :) )

[@joejeetha]

I don't think we should do an array clone. all the value transfers can be in the one nested loop.

[@anojk1]

Thanks, Irfan. Remarkable work, every effort you put in this is appreciable.

[@AyushRaj-gf2ce]

could understand the logic while the video of tushar roy...and you made me understand it so easily..great explanation! subscribed and looking for more questions on graph and dynamic programming

[@fatcatgaming695]

Absolutely love these, the time is spend going over and explaining the problem / solution is invaluable. Thank you.

[@prateeksaxena7808]

Please post more video lectures for coding questions.

[@TonyStark-lg7ux]

for the first time i subscribed a channel before looking into number of subscribers. great work, u are an excellent in terms of teaching anything.

[@addtextapp]

Really great explanation, thank you. One important case: when matrix has only 1 row/column the result must be assigned to 1 if there's at least one occurrence of 1.

[@titouant1936]

just begin your 2 for loops at i=1 and j=1 so you don't have to test for them to be zero.

[@arturo9790]

However if the entire matrix is composed of 0s except for a 1 at index 0,1 , then starting at i=1 and j=1 will never look at this element, and would output that the largest square is 0. However it should actually be 1.

[@arafathossain4794]

This comment holds more value than the actual video

[@janesmith8561]

This video was so helpful thank you! In the future could you please go over how you came up with a solution instead of just jumping into it? Also I was SHOOK when you looked directly into the camera for the first time during the interview.

[@IrfanBaqui]

Jane Smith Haha, I should look into the camera more in that case 😆 And I'm glad you found it useful. I'll look into explaining my thought process even more, thanks for the feedback.

[@TigraStyle]

awesome explanation, thanks for this!

[@7810]

The solution is so graceful and well explanatory! Many thanks for the lesson.

[@serhiypidkuyko4206]

Hi, Irfan. Thank you for your video-task and its very smart solution. But: 1. that solution isn't good (not optimal) when the matrix has only a few zeros. For example if matrix has no zeros the solution could be found much more faster (the corresponding solution based on calculation the maximum square with up-left value=1) 2. you don't need to create one more matrix - just one-dimensional array (one line or one column of the given matrix) will be fine. So if your initial (given) matrix is m times n and m

[@crothert]

ty for helping me prep for interview

[@eduardopetry911]

Thank you for accepting the feedback! Great video, the problem presented is solved in a very interesting way. I'd like to contribute with subtitles, can you enable acceptance of contributions from viewers?

[@IrfanBaqui]

That would be amazing! I just enabled accepting contributions. Looking forward to seeing yours.

[@MrThepratik]

Nice one Irfan Have been looking for different approaches for dynamic programming . This really helps a lot !!

[@niharikaepuri3305]

Sir, your videos are really helpful. Please upload videos like this more often.

[@fredschneider7475]

Nice elegant explanation, Irfan!

[@chiraggupta1557]

you are a great teacher..i understood it thoroughly! thanks a lot & keep posting :)

[@chenyangwang7232]

A posted solution is good of course. The thing is how to come up with this solution. What if we didn't see this or a similar question before during the interview?

[@vatsalanarang]

Your videos are great and the explanation is helpful, could you make more videos on interview questions.

[@Ashish.Shukla9]

what if we have to find max size of rectangle that can be formed....any idea???

[@rongrongmiao4638]

You should return result * result for the area. Currently you have the maximum length of the square. : )

[@vrezhgulyan6834]

Rongrong Miao He is returning the min of the neighbors + 1. The question asks for the largest square, which is the length of the height or width which are equal. The question doesn’t ask for the area.

[@itarukishikawa6845]

def largestMatrix(arr): size = len(arr) result = 0 arr2 = arr.copy() for row in range(1, size): for col in range(1, size): if arr[row][col] == 1: arr2[row][col] = min(arr2[row-1][col-1], arr2[row-1][col], arr2[row][col-1]) + 1 result = max(result, arr2[row][col]) return result With less code in Python

[@axeliuxTEC]

Do you need the cache at all ? Looks like we could just override the array. Obviously in real application you might just need to find the area without messing around with it by overriding it .

[@safiyapathan7510]

B: Tips to ace your coding interviews It would be very helpful!

[@omgtruth171]

Dude you are the best teacher in DP I have ever seen! Could you do another DP problem: minimum score of polygon triangulation?

[@RohanDaDev]

If you're given an array for the polygon's, sort the array and return the numbers from indexes 0 to n-2 where n is the length.

[@vaibhavshukla2658]

Great Explanation Irfan

[@pranavkumarsoni7518]

very great explanation.

[@TM-qc5oz]

What is the intuition behind considering a 1 to be in bottom right instead of top left, for the iterative solution ?

[@SaurabhNarhe]

You are doing really great. Helping me learn so much. Thank You!

[@xenky0]

Thank you Can you explain why can you lead to conclusion that: M(i,j)=min(of neighbors) + value(i,j) I cannot understand the reason. Thanks.

[@sojuthomas7727]

very difficult problem. but I understand your explanation s.

[@MickaelBonfill]

This is nice but I thought you will present a solution to get the largest square (I mean it's coordinates in the given space or matrix). I think to get the coordinates it shouldn't be harder, maybe cache the indexes i and j when you pass in your (currentResult > result) statement ? I don't know if it's better than an algorithm using a voronoi diagram where each voronoi vertex is a 0 from the matrix, then use something like the Largest Empty Circle but for Square to find the coordinates. I think for big matrices this is something to benchmark.

[@jigaurafael6974]

You have the result, thats 3. Just search it in the cache matrix, memorate the row and the column of the result, in this case its (4,4). Then you extract 3 and you have the start of the square matrix inside, and ofcourse number of rows and columns will be the same as the result, 3.

[@jigaurafael6974]

Pretty much the same that you said

[@sid007ashish]

Can someone clear my doubt? Why is this one dynamic programming? Is it because of the cache(memoization)?

[@ujurak3899]

Is a cache really necessary here? It seems modifying the matrix in place has no deficit to performance.

[@pinaksawhney4941]

Thank you so much. keep doing videos like these!

[@kambalavijay6800]

Since we don't do anything when i=0 or j=0 why don't we start from i=1 and j=1? Just asking

[@apratimtiwari5555]

Amazing explanation!

[@yuanyuanliu7439]

very clear! great explaination!

[@rohit236c]

really great video man!

[@arupnaskar3818]

very smart and good logic sir.....

[@johnsonhan2000]

You are so underrated.

[@SudhanshuSrivastavaIndia]

Fab Irfan... you made it easy man.. Thanks

[@satishshingade8514]

very nice explanation thank you

[@uneq9589]

The implementation was quite easy!

[@iarjun1773]

Your explanation is nice I really like it. However, I just want to know why you adopted this approach, like iterating through the neighbors. We already have a matrix and it consists a sub matrix of 1's. Can we go with any other approach? Is there any algorithm to find sub matrix in such a case. I will be very much thankful if I get an answer, since I have seen lots of example with the same approach as yours, however, unable to get the reason for doing so. Implementation was really easy anyways.

[@shivajunna]

I have one simple question! How do you come up with the instantaneous solution??? How is it possible? What needs to be done to be at that position?

[@john_rambo_27098]

:)

[@xenky0]

Yeah I did not understand the process of finding the optimal structure for this problem, can anyone explain to me?

[@myhomeariboyina9606]

A, B and C in same order you have given

[@chikinfrydsteak]

Very helpful! Thanks so much

[@chloekimball536]

How can this method be extend to find submatrix with the largest sum? (now matrix has both negative and non negative values)

[@ditikrushnagiri5622]

Thanks , Irfan .

[@laventin4332]

very elegant

[@sinhamohit]

Great explanation. Thank you.

[@researchandbuild1751]

Ive been watching a lot of these interview videos and it seems like so many of them are the similar type of problems always needing recursion "largest item" type of problems

[@just4uchin]

Please make one on 0/1 Knapsack problem

[@sarcastitva]

Smooth as butter.

[@alisheheryar1770]

Sometimes I got zoned out. Nice effort but still room for improvement.

[@joydas1685]

Simple and clear explanation Keep on bringing more coding problems like this..

[@chuckywang]

How did you come up with the intuition to form this solution?

[@cwagnello]

You need to return the max size of the square. Right?

[@nspranav]

Thank you. can you also show the recursive way of doing this.

[@sakshamchhimwal322]

Clear Concise Awesome!!!!

[@kid_kulafu_1727]

Hello. How is this optimal when your using inner loop. Run time O(n**2) even though you cache it. I will work for every J right? Sorry im so noob. Thanks.

[@huyvole9724]

Thanks. More video plz.

[@harshhundiwala4621]

Awesome explanation

[@Xellos976]

Great videos! Can you increase the volume of the interviewer next time?

[@PowKu10]

LeetCode 221， nice solution！

[@walterwhite6499]

So, when you start at i = j = 0, won't i-1,j would give an out of bounds error?

[@watcher_109]

Its explicitly checked for i=0 & j=0 and the same value as the matrix is copied to the dp array.

[@nikhilb3880]

Interviewer will be like, "why are you explaining me the problem?"

[@BrentSnider]

Great video

[@jugsma6676]

WOW, That was so nice.

[@chinmayanand896]

good work brother....

[@jamsrandorjbatbayar3652]

Thank you very much!

[@wucas123]

Well done!

[@lokeshwaran5650]

Best way of watching

[@Steve-ft8ux]

well explain, thank you

[@shiriusmt]

I think instead of cache[i][j] = 1 + min(...); it should be cache[i][j] = matrix[i][j] + min(...); right?

[@jaivasani3773]

Either of them would work. He is using 1 because he already knows that the value for matrix[i][j] is 1. See the condition else if (matrix[i][j] > 0). This means that the value is not zero, that means the value will be 1. Hope this helps.

[@vartikasharma2598]

Yes, matrix[i][j] is probably a better generic answer if you are looking for a generic solution like longest increasing subsequence.. but for this question matrix[i][j] =1

[@xenky0]

I dont understand why min() ??? Can anyone explain it?

[@yashmehta7196]

Did he really have to wear white

[@ajaypilaniya8562]

What if we need to find largest rectangle?

[@yoyonel1808]

For area of the largest rectangle (in submatrix of 1s), you have to use the solution to find the max rectangle in histogram and some Dynamic Programming logics. It's not hard to solve when you have the solution for the problem: "Largest rectangle in an Histogram")

[@tusharchauhan2019]

How did u come with logic??

[@jeff4615]

Nice video