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

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

[pascalfragnoud]

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.

[davidjames]

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.

[arunkumarm]

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<=N


Constraints
1<=N<10^4

0<=x<10^4

Output
Value of n where nxn matrix is the largest one embedded in the stacks.

[dvdh]

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

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

[angelv.g.]

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.

[paritoshpradeep]

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.

[analogylibrary]

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

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

[kambalavijay]

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.

[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

[TonyStark-lgux]

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.

[Shini]

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.

[shashanksingh]

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

[AyushRaj-gfce]

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

[yannicbrandstetter]

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

[jakelazareth]

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

[owaiswasim]

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

[anojk]

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

[ajaikumar]

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.