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

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

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.

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.

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

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.

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

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

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.

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.

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

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

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

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

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

ty for helping me prep for interview

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

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

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

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.

Thank you so much. keep doing videos like these!

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

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

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

Great explanation. Thank you.

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.

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

awesome explanation, thanks for this!

very smart and good logic sir.....

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

really great video man!

Nice elegant explanation, Irfan!

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

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.

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

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

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

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.

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

Awesome explanation

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

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

Please post more video lectures for coding questions.

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

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

Great Explanation Irfan

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.

Amazing explanation!

very clear! great explaination!

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.

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?

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

very great explanation.

Thanks. More video plz.

very nice explanation thank you

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

Very helpful! Thanks so much

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.

Please make one on 0/1 Knapsack problem

awesome explanation

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

How did u come with logic??

WOW, That was so nice.

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?

"mhm"

You are so underrated.

perfect way to approach a DP problem

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

The implementation was quite easy!

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.

very difficult problem. but I understand your explanation s.

good work brother....

Well done!

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

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.

Amazing!

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.

Thank you very much!

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

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

I need answer for this question Given an array of Given an array of N integers where each number a[x] indicates a stack of cubical bricks of height a[x] Essentially the array represents N stacks of bricks. The goal is to determine the largest nxn matrix (square matrix ) embedded in this array of stack Input format: First line indicates the size of the integer array say N Each of the next N lines represent the height of the stack at index x where 12,+x

well explain, thank you

Smooth as butter.

Thanks , Irfan .

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

Great video

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 .

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?

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

very elegant

WOW !! Quite impressive :) !!!

thank you!

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

Nice video

What if we need to find largest rectangle?

Awsome bro

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

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

so good.

Best way of watching

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