Lucky Numbers in a Matrix - Leetcode 1380 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve lucky numbers in a matrix I actually really like this problem because I get to show off some of my math skills again and I'm actually going to show you two solutions so the first solution is going to be relatively not crazy I mean I guess for an easy problem maybe it's a little challenging it's going to of course given like a matrix like this of n by m Dimensions at the very least you can expect that you're going to have to at least iterate over the entire Matrix so the solutions time complexity is going to be this the space complexity is going to be n+ M now the second solution is going to be a lot more interesting and you can guess which of those two we're going to optimize we can't really optimize the time complexity so we're actually going to get the same time complexity but the space complexity is going to get down to constant and I'll kind of walk you through my exact thought process for that but let's just get into the question first of all we're given a matrix that could look something like this I guess uh in this example we actually don't need the bottom row but the idea is we want to sort of identify lucky numbers a lucky number by definition has to be the minimum number in the row so if this is the minimum in the row there's no way any of these numbers could be lucky this is the minimum in the second row there's no way any of these could be lucky and this is the minimum in the third row there's no way any of those could be lucky now at the same time the number must also be the maximum in the column so looking at the original column I mean I cross these numbers out but we do need to at least look at them to see that this is greater than all of them which clearly it's not three is not larger than 10 or 16 so it's not a lucky number I'm going to cross this one out as well so just to make it a little more clear like this what about this one one is it the largest in the column no so again cross it out lastly is this the largest in the column so this is the only lucky number in this Matrix and so we are returning all the lucky numbers in the form of a list it's a little bit misleading and I'll get into that that's a bit of a hint I guess but uh sorry so we'll return 15 in the form of a list that's the solution for this problem now how exactly could we have coded up a solution like that well not too differently than I presented it the first first phase of the algorithm would be get the row minimums and I'm going to actually do them in the form of a hash set so if we collect all the row minimums in the form of a hash set the problem becomes not too difficult because if we have all of them so in this example it's going to be something like 1 3 15 these are the row minimums now getting the column maximums is going to be a bit more tricky but we can kind of follow the same process process so let's kind of do that as well I'll Circle those in green this is a column Max this is a column Max this is a column Max and this is a column Max this time they're all on the same row but you know it didn't have to be like that but anyways these are the column Maxes 15 16 17 and 12 at this point the fact that I drew this out can you tell me what the solution would be or maybe how you could Cod it up or maybe even why did I say I'm going to collect these in a hash set because now we can easily find the intersection if I have two circles these are the column Maxes this is not a butt cheek by the way I'm sorry if it looks like that these are the column Maxes these are the row minimums I just want that sweet sweet middle because that's the intersection those are the numbers that are the minimum in the row and maximum in the column and in this case in terms of coding it it could be pretty easy you just iterate over one of them and just check is one in this nope it's not so this is not it is three in that nope 15 is the only one that belongs to both of them so 15 is the result this is n * m space n+ m or sorry n * m time and N plus m space but I'm actually going to show you a little trick you can actually optimize the space a bit to get it down to the max of n m so I always like to get the dimensions of a matrix just to make my code a little bit readable so we'll do that like this and I'm going to have the result which is going to be a list and we're going to return that list but not before we actually add some values to it so first I'm going to have a hash set for row minimum and then I'm going to find the minimum in each row believe it or not you don't need a nested for Loop in Python to do that but the time complexity isn't going to be improved basically I'm just saying that from a given row we can get the row like this Matrix at this row and then we can get the minimum from it just by calling the minimum function on this array and then we can append or add that rather to the hash set that we have up above so that's phase one phase two is going to be collecting the column Maxes also in a hash set that's going to require nested Loops just because the way a matrix is kind of structured in code we can't really get an entire column so we have to do this column in range columns I'm going to declare the current Max as the value at the beginning of this column so I'm going to say the column is like this and I want the value at index zero we could have picked any value it doesn't really matter but I know that zero is always going to be a valid index so now for our in range rows we're going to basically just try to maximize this so I'm actually going to copy and paste it it's going to be pretty similar I'm going to take the max here of current Max as well as the value that we're currently looking at so replace this zero with an r and then we're good and at the end don't forget once you actually compute that Max in this particular column make sure to add it to that hash do this do add the current Max the last phase is relatively simple we just go through a number in either the row Min or column Max every number in that so I'm going to do row Min and if this number is in the column Max as well it's part of the intersection we can append it to the result just like this and that's the entire code I'll run it you can see it's accepted and even the memory is actually pretty efficient but I'm going to show you a small little optimization why did we need to add this element to a hash set could we not have just asked the question if it's a part of the intersection like down here just so you know this will work if I swap this here and then I put row Min down here this will also work so every time we have a number that happens to be a column Max why not just ask the question if current Max is in row minimum set if it is then append it to the result like this and then we don't need this bottom one and we also don't need the column Max hash set so just a small little optimization doesn't really improve it much but you can see that this solution does also work this time I mean Leo give us less memory okay whatever it doesn't really matter but we can actually improve this further and the idea I'm going to use is once again the idea that you always use when trying to implement a greedy solution I'm going to show you why this solution works with a math technique called proof by contradiction first allow me to explain something when I first actually read the problem description I thought it was asking us to find the max in each row and the max in each column that's what I thought and then I I tried to think well how many solutions could there possibly be because if I find a Max here in a column like if I found a Max in this a row for example then I'm eliminating everything else because only the element that's a Max in the row could be a lucky number and also if it's the max in the column then I'm eliminating all of these so at most you can imagine something like this where okay let's say just hypothetically if this was the max then we'd have something that looks like this and then cross these out as well and then the only two elements remaining are here so either of them could be the max this time it's this one and then we would cross out everything in the row and everything in the column if we were looking for Maxes it would be limited based on the dimensions of the grid whichever one of these is smaller this time it's three so you could only have up to this many lucky numbers but actually our problem is a little bit different we're looking for the Min in each row and the max in each column first I want to mention that every number in the grid is going to be distinct I should have probably mentioned that earlier but that's kind of why we're not going to run into like the duplicate case where there's multiple elements that are like the max in a column or minimum in the row second consider this we have in this example a number 12 which is the minimum in the row so of course none of these are going to be lucky and it's also the max in the column none of these are going to be lucky either but let me take some notes these three numbers are greater than 12 this is the note I'm making so these three numbers are greater than 12 these two numbers are are less than 12 they have to be right so for any number in this remaining region to be lucky they have to be greater than 12 because all of these numbers are greater than 12 and if these numbers want to be lucky they have to be great like the greatest element in the column so these numbers have to be greater than 12 but they also have to be the minimum in the row and these numbers in the same row as them are less than 12 so they have to be even smaller than those numbers so how can these numbers be simultaneously greater than 12 and less than 12 this is a contradiction so therefore if we have a lucky number there cannot possibly be more than one lucky number at this point we actually know enough to solve the problem in concept in space I want to take it a small step further and prove to you that there doesn't have to be exactly one lucky number there could actually be zero lucky numbers given a matrix because consider this example here there's only going to be one minimum in each row we've identified them but this number is not the maximum in the column neither is this one but this one is because every value in the column is actually less than 12 but it didn't have to be that way all we have to do is think of one counter example and we prove that there doesn't have to be a solution so if I change this to 22 and I change this to 27 this is still the minimum in the row this is still the minimum in the row and this is still the minimum in the row but this is not the max in the column neither is this and now neither is this the max in the column so we've eliminated everything there is no result for this problem and it kind of hinges on the fact that every number in The Matrix is going to be distinct sorry I probably should have mentioned that at the beginning but I do think the problem description mentioned it so I just want to show you this counter example because none of the examples in the problem description show you that actually there doesn't have to be a result now lastly let me prove how we can find the lucky element and how we can do it with constant space so it all hinges on the fact that if we've identified the minimum in each row among those three it's actually impossible for the smaller ones to be the lucky element only the max of the three could possibly be a lucky element and it's possible that even the max might not be a lucky element for reasons I talked about just a second ago now why is that the logic is pretty similar consider this if this element is the minimum element in the row but in the next row there's a minimum element that's greater than this one if this is the minimum element in the row we know that 1 is less than three we also know that three is less than every other element in the row in this case 9 87 I'm really sorry if you can't read this I'll write it over here we've shown this right three is less than all of these so at least one of these elements is going to be in the same column as one it could also even be this element this element could have been in the same column as one as well but for one to be lucky it has to be greater than all of these which is obviously not true given this inequality so basically we ruled out one we can use a similar process to rule out three if 12 is the minimum in the row there must be at least one element with the same column as three that's greater than three so three can't possibly be the max in the column therefore only the max of all these minimums could be the result so the algorithm is going to be this this identify the minimum in a row identify the minimum in the next row and keep track of the maximums of all of these so right now we'd say Okay three is the max get rid of this and then in the next row we'd say Okay 12 is the max of the minimums we've seen so far so this is the only one we keep track of there are many ways to code up the remaining you could just go through every element in that column it might actually be more annoying to code that up so another thing you could do is just you know iterate over the grid once more find the max in each column and if we found the max in a given column and it's the same number as the lucky or the you know the previous number we identified then we found the result we' return immediately otherwise we'd you know keep continuing if we never find that result then we just return an empty array at the end so that's how we can get it down to constant space let me Cod it up starting with a little bit of boiler play I'm going to do this I'm going to maintain the max of the row mens that's the kind of special number I was talking about since we're trying to maximize it I'm initially going to set it to float negative just a really small number so what we're doing is remember first find the minimum in every single row kind of like we did before I'll call it the row Min but we want the max among all of the row minimums so we can set max of row mins and set it to the max of the one that we just found as well as itself so after that we'll have what we want and then we'll start going through the columns so I'm going to do it like this for column in range columns and I'm going to keep track of the column Max so I'm just going to take an arbitrary element from the current column I'll pick index zero just because it's easy and it's guaranteed to exist next we're going to go through every Row in that particular column and we're going to try to find the column Max so maximizing column Max as well as the Matrix at row and column now after that we will say that if the column Max is equal to the number we saw earlier then we found the solution it's the number that's the max in the column and the minimum in the row so go ahead and return it I'm going to do this one CU it's shorter I mean they're the same value but this one obviously it's a shorter variable name so at that point we return it's not guaranteed that this is going to execute so make sure to have a return statement down here I think leak code will actually pass it even if you don't have this in Python because they do some weird type conversions or whatever but I think it's you know smart to have this let's run it okay I had a typo really sorry don't know why I put columns here I'll call it rows try it again okay now you can see it does work and it's efficient these run times are pretty random though if you found this helpful check out NE code. launched python for coding interviews a couple days ago and I'm really looking forward to the stuff I'm going to launch next it's going to be even more exciting