Largest Square of 1's in A Matrix (Dynamic Programming)
HTML-код
- Опубликовано: 9 сен 2024
- Check out the detailed data structures and algorithms course at www.interviewa...
Dynamic Programming - A ridiculously simple explanation.
In the video, I show you how we can turn a complex coding interview question into a simple one through dynamic programming.
The problem is also known as 'Maximum Sub Square Matrix' - Given a matrix of 0s and 1s, find the biggest sub-square matrix entirely of 1s.
Music: Modern Theme by Nicolai Heidlas
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.
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.
Dude you are one of the best thing that happened to RUclips (For Programmers atleast :) )
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.
Good one but different too. Actually the idea of explaining on board like you are being interviewed earned my subscription.
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.
Perhaps the best explanation I've seen for this problem. Thank you!
Thanks, Irfan. Remarkable work, every effort you put in this is appreciable.
i was trying to understand this problem , and No one did explain this problem better than this guys(Iterative Approach). you are awesome IrFaN!
Space complexity can be reduced to O(N) by only keeping track of the previous row and the current row of the cache.
Or it can be O(1) if you just modify the matrix given to you.
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.
pls give the interviewer a mic or put him closer to the cam
This is the best step by step approach i have found.. Thanx!!
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
perfect way to approach a DP problem
awesome explanation, thanks for this!
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.
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.
I used the same technique in my Computation Fluid Dynamics class...
you are a great teacher..i understood it thoroughly! thanks a lot & keep posting :)
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.
Nice one Irfan
Have been looking for different approaches for dynamic programming . This really helps a lot !!
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.
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.
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
Absolutely love these, the time is spend going over and explaining the problem / solution is invaluable. Thank you.
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
ty for helping me prep for interview
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.
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.
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
Nice elegant explanation, Irfan!
very great explanation.
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 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?
That would be amazing! I just enabled accepting contributions. Looking forward to seeing yours.
"mhm"
very smart and good logic sir.....
awesome explanation
You are so underrated.
very nice explanation thank you
Clear Concise Awesome!!!!
really great video man!
You are doing really great. Helping me learn so much. Thank You!
Please post more video lectures for coding questions.
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
I don't think we should do an array clone. all the value transfers can be in the one nested loop.
Great Explanation Irfan
very clear! great explaination!
B: Tips to ace your coding interviews
It would be very helpful!
Thank you so much. keep doing videos like these!
Amazing explanation!
Fab Irfan... you made it easy man.. Thanks
Great explanation, thank you.
just begin your 2 for loops at i=1 and j=1 so you don't have to test for them to be zero.
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.
This comment holds more value than the actual video
Very helpful! Thanks so much
Your videos are great and the explanation is helpful, could you make more videos on interview questions.
Dude you are the best teacher in DP I have ever seen! Could you do another DP problem: minimum score of polygon triangulation?
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.
Great video
what if we have to find max size of rectangle that can be formed....any idea???
very elegant
very difficult problem. but I understand your explanation s.
Smooth as butter.
The implementation was quite easy!
Amazing!
Well done!
Thanks , Irfan .
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
Simple and clear explanation
Keep on bringing more coding problems like this..
You should return result * result for the area. Currently you have the maximum length of the square. : )
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.
Nice video
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
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.
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.
Pretty much the same that you said
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.
Thanks. More video plz.
WOW, That was so nice.
LeetCode 221， nice solution！
Is a cache really necessary here? It seems modifying the matrix in place has no deficit to performance.
good work brother....
Thank you very much!
Can someone clear my doubt?
Why is this one dynamic programming? Is it because of the cache(memoization)?
well explain, thank you
Interviewer will be like, "why are you explaining me the problem?"
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 .
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?
What is the intuition behind considering a 1 to be in bottom right instead of top left, for the iterative solution ?
Great videos! Can you increase the volume of the interviewer next time?
Sometimes I got zoned out. Nice effort but still room for improvement.
WOW !! Quite impressive :) !!!
Best way of watching
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.
Thank you. can you also show the recursive way of doing this.
How can this method be extend to find submatrix with the largest sum? (now matrix has both negative and non negative values)
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
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.
Epitech Rennes rpz
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?
:)
Yeah I did not understand the process of finding the optimal structure for this problem, can anyone explain to me?
thank you!
How did you come up with the intuition to form this solution?
You need to return the max size of the square. Right?
so good.
Please make one on 0/1 Knapsack problem