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

hey guys really excited for today's video because it's about dynamic programming the question is that if you're given a matrix with ones and zeros how do you find the largest possible square made of just once now the problem may seem a little complicated but just watch till the end and how simple the implementation is so let's dive right into it so we have this matrix and I have to find the largest possible square made by just once okay and the matrix can be of any dimension yeah okay so in this example then the answer would be 3 I'm assuming and also any index which for example largest possible square for this particular index let's say this index is a top left corner right would be one which is just itself right yes okay perfect so the first solution that comes to mind is perhaps I can iterate through this entire matrix and find find for each individual index what is the largest size but that would be very inefficient so the second thing is we just I just mentioned that this is a top left corner of the of the square right so in order for me to get the answer for this particular square let's say when I'm when I'm talking about this one and this is one then the answer would be 4 over here right because that is or 2 sorry but for ones that make 2 so if I were to go through this logic then I would say ok I have 1 over here let me just make this 0 again I have 1 over here in order for me to get the solution for this particular index when I say solution for this index basically if this index is a top-left like for the square over here at the top left corner of the square how big of a square it can make such that all of the elements in the square are once so I would say ok let me look at my right my bottom right and my bottom one if all of them are ones let's say this is a one then I would take them then the answer would be 2 right in this case which is basically whatever is the value of these 3 plus itself right so 1 plus itself now if this was 0 then the value would be 1 right because maximum square then can make is just itself so in this case this would be 0 which is the minimum value of its neighbors plus itself right so anytime then if we consider this as the top-left corner of the square any time I want to check how big of a square of once this can make then I will need to recurse on these 3 neighbors to see how big of squares that they can make suppose I have the solutions the recursive solutions of these 3 and this one says ok I can make just hypothetically ok not relate to that matrix I can make a square of size 3 this can say this says I can make a square of size 4 but this still says I can still just make a square of size 0 like I can make a square at all then the answer would still be minimum of these 3 which is 0 plus itself which is 1 right and obviously if this is 0 then this will be 0 plus 0 which is 0 right so let's see actually if this is 0 then I won't even consider it right right yeah because of its 0 then wouldn't make sense for it to make a square right so let's see how we can how we can do this over here so as mentioned in order to compute the value for this particular index I will need the value of this this and that's right so this is an this a recursive solution in order for me to complete the value of this one I'll need the value at this this in this one actually looks like I'm computing the value at this particular index twice and actually if I want the value at this one and then I'll have to recompute the value over there so I'm actually computing it more than twice so it's not very efficient so this kind of triggers that perhaps this is a good candidate for dominant for dynamic programming right so let me erase this let's think about this in a dynamic programming way obviously I'll need some form of cash right for for this let's say as I'm computing this three times I don't want to do it so I store it somewhere and as these values then would be independent for each of these indices I can just have a matrix of the same length and width or the row and columns as this one now as our cash so let's say I have a matrix over here which is one two and three and one two three right and four actually yeah right so if this is my cash yeah I say okay for me to compute the value do I need it one two three four five one two three four five yes well needed right okay so in order for me to compute the value for this particular index I'll say okay let me recurse on this one this one this one and as I'm rehearsing let me just save that value in the cache so next time when I want to compute the value of this I'm looking at at the value over here I say oh I don't need the computation I'll just return whatever I have in the cache so I track the cache first and then if it's not there then I compute it and then save it right in the cache again right so this is a solution that I'll move forward with it's a recursive solution it's just our way to go around or can you make it to do can I make it iterative I can I can make it a trait of us as well actually so I will just need to iterate through all these squares all these indices and compute their own values but obviously now as I'm iterating through them I will ideally want to leverage the values that I've already computed to come up with weight with its solution so actually then if I'm iterating I should consider I should consider each one of these indices not as a top left but as the bottom right so right now I was saying okay for this particular answer I need the answer to this this in this one right now if I'm iterating I'm going from zero to whatever is the length minus one when I'm at this particular index I don't really have the computation for these three yet right so I can say okay instead of me counting the index as the top left corner let me regard it as the bottom right corner right so if this is if this index is a start is a top left of our matrix itself then I start over there right and as I'm at the top left and that is the bottom right of our of our square or the maximum squared can make then the answer is just itself then this will be one same thing over here so I think the the the leftmost column and the topmost or all the answers for those will be just itself then considering they are the bottom right corners yes of the square so I'll have zero over here and then when I'm here I know the answers to these three neighbors I can say okay in order for me to compute my value I need the minimum value of these three so now the logic is the same and the minimum value of these three plus the value of myself so it'll be 0 plus 1 which is 1 right so the answer for this particular index will be will be 1 so let me just erase this right now if it's 0 then I wouldn't I wouldn't go to the computation so let me just go through an example over here and then I'll go through the actual implementation if that's ok so I start I start let's say I equals 0 and then so I 0 and then I'm just trading through all of the columns right so I equals 0 and J equals 0 right now so I'm over here and I say ok what is what is actually when I equals 0 and J equals 0 then it is just itself great I don't need to do anything if either one of these indices is 0 then the answer for the maximum square will just be itself so I say ok this is 1 this is 0 this one is 0 right now I'm in the second row so now sorry why the answer will be itself so if this is the bottom right corner then I'm looking in its neighbors neighbor over here neighbor over here neighbor over here but these three fall outside of the matrix right they don't exist so the maximum it can make is just itself if I'm over here then same thing one of the neighbors is falling outside so anytime one of the neighbors fall outside of the matrix then the answer will be just itself because the minimum will be 0 yeah any time the neighbor is outside then that values 0 okay so in this case now I have all these values right then this 4 when I equals 1 and J equals 0 still one of its neighbors is outside so that is itself now I'm at 1 Yeah right I see okay I already have these to be computed so I take the minimum of these three and I add one to it so this will be 1 because minimum zero right and then I go over here the minimum of these three I add 1 to it I go here this 4 this one same thing minimum of this we have I add 1 to it same thing over here I add 1 to it right sorry this is zero so I don't even compute it good good catch I wasn't even looking at the matrix okay now I'm back over here now J equals now I equals 2 and J equals zero again right so anytime J equals zero or I equals zero it's just itself so I add 1 over here same thing for this one I'm computing it as it's 1 in this neighborhood 0 this will be 1 right but for this now it will be the minimum of these 3 which is 1 and then this guy is 1 as well so this will be 2 so because I'm making this square over here side 2 considering this as the bottom right corner yes now as I progress forward I'm here right now I look at okay its neighbors and this is 1 as well so the minimum over here is still 1 so I'll just have 1 1 plus 1 is 2 right yeah so this will make this square right here yeah we add 0 so I won't do anything and for all these bottom ones for all these bottom ones I have 0 over there because J is equal to 0 and this will be 3 right and for all of these I'll just do the same thing again so 0 1 1 so this will be 1 1 1 2 so this will be 2 for this one it's two to two actually right so it'll be 2 minimum is 2 plus 1 so this will be 3 and the last one is going to be 0 plus 1 so it's itself so in this case our max value is the value right there so actually as we're trading through it we can also keep track of the max as as we're going to the iteration so at the end we just return that value so let me now go into the implementation let's say I have a function and I say the name is largest square it takes in the matrix right now the first thing I need to do is form a cash so let me do that it's a cash so this is pseudocode cash equals an array let's say an array of length matrix dot length and it's an array of arrays right so matrix 0 dot length all right so actually if this was JavaScript I would actually have a for loop and go through populating the values as the inside of the cash just to make sure that it's particularly but for now pseudo code let's say this is basically a clone of the matrix itself yeah so let's say we are now also initializing max so max or let's just call a result right because it's going to be a result that we return at the end result equals 0 initially and then I go into a for loop I equals 0 I is less than say matrix dot length and I plus plus yep and then I have an inner for loop J equals 0 j j is less than matrix I dot length and J + + yeah okay so now what do I do the first thing I do is I check whether or not either I or J 0 if they are 0 then I don't do anything so I say if I equals to 0 or J equals to 0 then I say cash I J so ideally I would actually clone I would have the cash as a clone of the array itself because as we are iterating down we are sure that we are modifying the value so it won't really matter so let me just simplify this a little bit ok I'll say this is just a clone of the array or the point of the matrix so I'll say matrix dot clone exactly yeah I'll have a for loop and I will populate the new one with the same values so I have matrix dart clone so in this case now if this is the condition and it's met that I won't do anything right now the second condition would be that now we have to check ok if this is not the case then what do we do so we say else if I or the mate or the value itself is not 0 then we do something right so I say if matrix I J is greater than 0 basically it's not 0 where it's 1 then what do we do we say cash i J equals we said we add one to whatever it is right because we know it's not zero anyways we add one to the minimum value of its neighbors so let me say min min of cash I J minus 1 cash I minus 1 J and cash I minus 1 J minus 1 right yeah so this looks good now I will close up statement and at the end I will modify my result so I'll say if so this is still inside the for-loop I'll say if result or if cash IJ let's say I J is greater than result then result equals cash i J yeah and this will close our four loops and after the for loops actually I'll just return the result and I'm done so return result and that's it yeah so in order for us to kind of increase the efficiency and not compute things three times we had to allocate some space right so you're compromising space for for optimize time complexity but essentially will have a n by n or n by M space complexity as well as time complexity because I have a nested loop yep thanks for watching guys today's video was an excerpt from a data structures and algorithms course that I designed specifically for you to a su coding interviews and I've spent several months on this based on the feedback that I've gotten and I've made so many revisions to make it just right it's not out yet if you want to know or just get updated when it comes out sign up on the link below and I'll let you know and next week I'm going to cover the problem where you have to find the maximum area of rectangles inside of a histogram so I'll see you next week [Music] [Applause] you

Channel: Irfan Baqui

Views: 123,225

Rating: 4.8005719 out of 5

Keywords: coding, programming, dynamic programming, Coding interview, whiteboard coding interview, data structures, algorithms, amazon coding interview, amazon programming interview, google coding interview, google programming interview, facebook coding interview, facebook programming interview, coding interview example, how to get a job at amazon, programming interview, whiteboard wednesday, whiteboard thursday, irfan baqui, maximum sub square matrix, interview, maximum size sub matrix

Id: FO7VXDfS8Gk

Length: 20min 43sec (1243 seconds)

Published: Thu Jan 18 2018