Maximal Square of Ones (LeetCode Day 27)

hello everybody I'm Rita and today I will do some speed coding problem name is maximal square I think it's about maximal square of ones in the grid today let's say I want to have some fun and I will try to do it as quick as I can and then explain it why would we use that algorithm and I want a some example test start find the biggest square with one's height and width of the grid if H is zero or matrix of zero is empty return zero I don't know if it's all out or not and now DP why do we do DP I will explain later and that size H by default filled with zeros enter it over rows columns will say the piece best square ending there if it is a one matrix of row call this one the P of Rockall is at least one but actually if both Row is greater than zero and College greater than zero meme of those two numbers and this is the hardest part of the count plus anyway answer is maximum of itself and appear from Holland sir I mean it's 40 assuming that assuming that it's correct it isn't output to expected for return it's Aria I tried to be fast I didn't even read the problem carefully and there is a mistake I print that it's free by free because I'm missing something here i misclicked should be 2 minutes now what happened first of all this is as you can see dynamic programming and by DP of I will hide the timer for me the P of RC is you might want to say best best answer best square up to position RC looking from top left corner 0 0 up to this what is the best score actually to be able to continue our DP it will be best Square ending at RC possibly we will be continued in the future and this is why it makes any sense to do this let's see it drawings this is example from the statement with answer being Aria equal to 4 this score how do we even get the idea that it should be dynamic programming dynamic programming makes sense if we can the answer best Square biggest score with ones for the full rectangle for the full input by asking a subproblem what's the biggest square in some smaller rectangle maybe this one for example if somebody told us here the biggest square is 2 by 2 or maybe 3 by 3 can we say what is the answer well what if that Optima squirrel lies somewhere like that we can make another query what's the biggest square in this thing but still we might miss the answer because the answer might hit our bottom right corner not in the case where this is zero but maybe tactically this would be the answer that we need to find so by asking the P about this blue rectangle and red rectangle we will not necessarily find the answer but will not find the answer only if the square ends exactly there so that's the idea we need to find the biggest square ending here maybe it's this one this one this one among those I want to ask how big square turns there and there are methods for that like prefix amps there is something like 2 dimensional prefix amps I will maybe cover that in some other video but what about using DP it would make sense you might think to say of course this all assumes that this is not 0 it's instead 1 because if it's 0 we know there is no square like like no yellow square that I drew a moment ago is good consists of just ones is that if this was 1 then I would need to say kind of how far I can expand to still have ones here it's bad you might say hi it's a bit similar to finding the bisque biggest scar ending here like here it would be 2 by 2 so maybe this thing will be free by free because if I see that this free by free is not good doesn't consist of once then for sure this 4x4 will not be good either and this gives us idea that the piece should be biggest Square ending somewhere the PIO from column for example for this cell will be among let's say blue squares I draw now what is the biggest square we've just once and here it will be this 2x2 thing in my implementation I remembered sight of such square so the P of this cell will be 2 and then the P of this cell should become free assuming that also those are ones and those are ones and to ensure that I actually took minimum of 3 numbers in my code we will get back to the code in a moment minimum of three numbers minimum of the P in those three cells what does it mean well if that's a now we use yellow as previous the piece if I know that this square 2 by 2 is all one's this 2 by 2 is all ones and this 2 by 2 is all ones so ending here anding here and ending there if all of them are filled with ones and also this is 1 then I have this big square free by free with ones it isn't the case here the P for this cell will just be 1 it means that here I just have this square because Square ending here is this biggest Square ending here is that minimum of those free values sites of those cars is site of 1 over here so the biggest I can get here is 2 that's the logic and some intuition how the hell we would just get that idea also you could just say well we have a grid and often in problems will integrate like going from top left corner to bottom right corner DP of IJ is the best score up to here ending here like if we wanted to maximize the total number of coins we get by doing this path going bottom going down all right every time we would define the P of IJ as the best path ending here so maybe the best Square and ik here that's some intuition last thing to do is to actually analyze what happens for this test and now this is a 0 so what is the P of this cell it is 1 it is the biggest Square ending here what is the biggest DP for this cell zero because even this cell is not good for this one it's one zero zero one and now here this could be - it would be - only if all those free numbers were one because it would mean those free squares are good so I am good as well but this is not the case this is just zero here again it would be too I take minimum of those three numbers in my code if all of them were one it would mean I can be - suddenly it is just a minimum of those three zero plus one myself it is one here it's one minimum of three but includes that sadly again one one one but if this was one instead then this would be a two it isn't the case but you know it could be so we still are with low numbers red is just something hypothetical something possible maybe in some other test this is one and here something new happens minimum of those three is one it means that each of those squares they are good and I am good as well - then this is two as well of those free notice if those free were all - it would mean that this is good this is good and this is good then I would be free it's not the case I'm just saying what would happen in another test last row one minimum of this this and that but those are zeros actually in my code I say only if row and column are greater than zero so you are not first row or first column then you might be bigger than this you might use those free values this is zero because it's zero this is minimum of those three numbers plus 1 so 0 plus 1 and this is 0 at the end of this simulation I hope this helped a little bit in understanding what the code does that's looking again what happened here I created an array aged by W hide by weight by default vectors are filled with zeros in just you know like alright DP of HW equivalent to this answer is initially zero every time when I see our ending here the best square is free I consider answer to be that at the end I will return its car because they asked me about Aria if I'm not one if digit here is that one then the default value of DP equal to zero after I create the array stays there otherwise initially I put that as one because I know at least I have square one and if this is not first row or column then add minimum of three numbers the thing on the left on the above me and left above me those free because I know as I said if those free the squares there and with size at least two then I am square with size at least free I hope you enjoyed that and the problem was it's now a bit easier to understand including the very important thing remember about that when you trade ask yourself do I understand why I would approach it like that next time when you don't solve a problem ask yourself that question so that next time you see this problem or something similar you will know Oh dynamic programming makes sense here and for two-dimensional print exams I will make some video in the future I guess thank you for watching and see you next time bye

Channel: Errichto

Views: 30,337

Rating: 4.944056 out of 5

Keywords: leetcode, coding interviews, google coding interview, programming, errichto, coding problem, coding, algorithm, array, dp, dynamic programming, matrix, grid, square, maximal square

Id: oPrpoVdRLtg

Length: 12min 8sec (728 seconds)

Published: Tue Apr 28 2020