Set Mismatch - Leetcode 645 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem set mismatch this is a pretty interesting one for an easy it definitely qualifies as that because there is a pretty trivial solution which is O of n time and O of n space but we can actually optimize this in a few different ways to get the memory down to constant time so I'll be showing three solutions in this problem we'll start with the trivial solution then we'll get to the space optimized solution and then finally we'll show the math solution which is also space optimized so the idea is we're given a set of numbers like this 1 2 3 4 so in the range of 1 to n where this is going to be positive so every number in the set is going to be positive but something happened we took one of our numbers in this set this time it's three and we replaced it with one of the other numbers in the set in this case it happens to be two so now we have this new set what we want to return is two values we want to return the new value that we put here and that's going to go first I call that the duplicate number because notice how it's always going to be a duplicate if we replaced this with one of the existing values then clearly we have two copies of it now also we have a second value the one that we actually replaced I call this the missing number and that's the second value that we return the order here does matter if return them in the opposite order you will fail the test cases okay so how do we solve this problem well what do you notice about two how is it different from the other elements well the count of it is multiple one only shows up a single time four only shows up a single time but this number shows up twice so I propose we use a hashmap count the occurrences of each value in the input and the one that has a count of two that's that's the one we return whatever x value has a count of two we return that as the duplicate number also whatever y value has a count of zero because this shows up once this shows up twice this shows up once but also the one that we replaced it never shows up its count is of course going to be zero so we can find the number that has a count of zero and put it in the second spot that's the missing number now when I say find the number how do we actually do that we can't simply iterate over this input array can we well I guess that would probably work for getting the count of two uh but what about why what about the missing number how are we going to count it we can't do that by iterating over the array instead what we're going to do we're going to iterate over the range from 1 to n inclusive so we will technically iterate over three and then using that three we will do a lookup in our hashmap to check the count That's How we'll identify the value that has a count of zero so this algorithm has two phases one is building the hashmap and second is that counting part that I talked about now let's code this up so I'm going to declare our result first off and I'm going to initialize it just to be 0 0 and the comments will definitely help you not get confused so duplicate is the one that goes first missing is the one that goes second and then we return so phase one is just to count the occurrences of each number number here and then put it in a hash map the easiest way to do that in Python is just like a built-in way actually it's called a counter it basically is a hashmap it will do exactly what I said it will count the occurrences of each number now if you want to of course you can code it up with a for loop it's not super difficult that's why I'm just kind of leaving it as one line now for the second part is where we are now going to iterate over that range I talked about from 1 all the way to n which is going to be the length of the input minus 1 one next we kind of do that check we check is the count of this element the I element equal to zero also we're going to check is the count of the I element equal to two these are both going to be handled pretty similarly if the count is equal to zero it's the missing number isn't it so we should probably put it in the second spot so let's do that result at index one is going to be equal to I same thing down here result here we go at the first position cuz clearly if the count is two it's the duplicate number so we put it in the first spot just like this and then we return so let's run this to confirm whoops that's my bad when I said we're going from 1 to n I probably should have made this a plus one so a good reminder not to rush ourselves so sorry about that and that fixes the issue so this works now let's get into a couple more interesting Solutions we used a hashmap to count the occurrences of each number so I might map to zero I might map to one it might map to two there were three possible values any of these could have mapped to their counts right there's a couple things I want to make very clear to you first is instead of using a hashmap maybe we can use the memory that we are actually given like the input now it could be possible we're not allowed to do that sometimes that can be considered cheating it's worth clarifying with your interviewer if you're allowed to do that in a real interview but in this case that's what I'm going to do now how am I going to do it obviously if we're iterating over this and we modify this that's kind of a problem we don't want to modify the data then we lose the data we can't read the data so we do something kind of clever it's a technique you might have seen in other problems the fact that we are given a set from one to n tells us everything here is going to be positive so what we can do is Mark some of these values as negative as a sort of flag for us because while the numbers are in the range from 1 to n the indices are in the range from zero all the way up to three in other words the indices are in the range from 0 to n minus1 being clever what we can say is that if we come across a value if we see one the value one we map that to the index zero if we come across the value two we map that to the index one we're essentially saying a number minus one is going to be mapped to some index okay and we use negatives to mark that so we've seen a one before we're going to mark it as negative now we're going to go to the index and Mark it negative the fact that it's the same position is just a coincidence so keep that in mind next we get to two so now we want to go to the index at 2 - 1 which is the same position which is again a coincidence but again we Mark that as negative we get here and let me actually uh clean this up but now we get here we go to the index 2 minus one which is here once again and now we mark this negative again so now it's actually positive lastly we get to four we go to index 4 -13 and we mark this negative as well now this is the really beautiful moment that you kind of notice I said every value has three possible counts it can end up with if you notice the element with a count of zero will never mark that corresponding position as negative it will stay positive remember the missing integer was three the position three is positive okay and the other thing we know a value can map to two that's the duplicate number we have two copies of two so we went to index 1 2 - one and we marked it negative twice therefore by the end of going through this it is also positive so the two positions that are positive tell us what are the missing and duplicate number now the only question you're probably wondering is how do you distinguish between the duplicate and the missing number there is multiple ways to do that the easiest is as we're going through and marking a number negative we know that first of all this one it was never marked this one was marked twice so maybe we can use that to our advantage how do we know if we're marking a number for the second time probably if it's negative if the number is already negative for example -2 and now we're about to mark it uh as negative again it becomes positive but before we do that we should check is the number we're about to Mark negative already negative if it is it must be the duplicate number when I say duplicate the number itself is not the duplicate the index that it corresponds to is the duplicate and since our formula was N - 1 is equal to I to get back to the original number we do I + 1 so we know the duplicate number is going to be the index 1 + 1 two is the duplicate number once you know that it's relatively straightforward to get the missing number so I'll just save that for the code but notice we didn't actually use a map we used in memory so we have saved space let's start by iterating over every number in the input what we want to do is Mark every value a negative what we want to do is take every number map it to the corresponding index so n minus1 now this we want to set it as negative so in Python that's pretty easy you don't even have to do any multiplication just the negative sign now we've done that that's great one thing I didn't show in the drawing explanation is if we're marking these values as negative it could be possible as we're iterating over the array we come across a negative number we probably don't want that that's going to give us an index error so before we actually try to use this as an index let's go ahead and just get the absolute value of it great now the only thing remaining is before we mark this position as negative we can check if this this number is already negative so is this actually less than zero right now if it is we found the duplicate number we can set result at 0 equal to n so this is kind of how I talked about it in the drawing explanation alternatively this isn't super important but if you wanted to you could do it kind of the other way so move this down here after the assignment and then just change the order of this uh again not like a big thing or anything now we have the duplicate how do we get the missing number well basically what we're going to do it's not super complicated just go over the array one more time and try to find the positive number there should only be two positive numbers in the array right now so try to find it now we don't know is this the missing number or is this the duplicate number so let's just check it in the if statement let's check this is greater than zero and it's not the duplicate number because what we're about to do right now we think we found the result we want to set result at in index one to the missing number again remember the missing number is not n itself it's I + 1 this is what we want to do but we can only do this if I + 1 is not equal to the duplicate number so we're checking that before we do this assignment and then once we find the missing number let's just return a couple uh typos really sorry about that one down here in the loop we want to add the keyword in and second here I don't know where I got this I from I'm sorry this should have been an n as well just like up above okay now let's run this and as you can see it works and it's efficient lastly let's look at the math solution if you try to come up with a math solution one of the first things you probably try is doing some kind of arithmetic with like the input set of numbers as well as the range from 1 to n some kind of arithmetic but we're not quite sure what to do we see that there's a matching pair of elements in every spot except for one so maybe if we do like subtraction we take input set of numbs subtracting by 1 through n and when I say subtraction I mean kind of taking the sum of this as well as the bottom obviously this is the only differing pair so we end up with a negative 1 what does this netive 1 represent it represents the duplicate number which I'm going to call D subtracted by the missing number number of course which I'm going to call M so this is a math formula but what you quickly find is this isn't enough to determine what the duplicate is or what the missing number is cuz we're not just looking for one number we're looking for two solving an equation like this is impossible but before you completely dismiss that a math solution might exist let's at least try to solve this we need a second equation I know a lot of you guys don't love math as much as I do so I'll give you a quick refresher when you have a system of algebraic equations if you have n variables in those equations you need n equations to solve that system of equations so if we have two variables but only one equation we can't solve it but if we get a second equation with those variables then we can solve it so let's try to do that we were clever in coming up with this because we know it represents the difference we know in all the other spots the values are going to be same so they cancel out we can do something clever again can't we and this part I admit it's not easy to come up with it's very much not easy to come up with but drawing it out definitely helps and watch this watch what I'm about to do one squared squared squared squared I'm going to put a square in every position so now what did I do well once again we know these cancel out the only thing that's left is this guy and at this point you might know where I'm going this is the duplicate number this is the missing number the duplicate number squared minus the missing number squared is equal in this case we can solve for it like this is going to be a number this is not a variable we have numbers to work with 4 - 9 that's ne5 to me and at this point it's all about algebra like if you're really really good at algebra you can solve this no problem like it's not about code anymore this is purely a math problem so I will try to kind of show you that so first what I'm going to do here is solve for one of these variables it doesn't really matter too much which but I will solve for D you guys know how much I love D so with M we will subtract 1 and we'll get D equal m minus 1 all I did here was just add M to this side add m to the other side so we ended up with this now what we can do is get rid of D in here instead of having d^2 let's replace it with M minus 2qu we will get M -^ 2us m^2 is equal to -5 so when you square this you get I think m² as well as POS 1 and I think -2 M and then minus m^ 2 here and we get -5 notice that this is the same as this let's cancel that out and with the leftovers we can do some basic math I think just subtract one from each side and then divide both by1 we'll get something like -2 m is equal to -6 and then we'll get m is equal to three the missing number guys is three okay what's the duplicate number let's go back to our first equation solve for it D is equal to 3us 1 there you go we have the result it just took you know a couple pages of math and algebra but we saved some space complexity so I'm going to do some comput remember what we're trying to do first is get those system of equations so X and Y are going to be my system of equations X in this case is going to represent the number that is equal to the sum well that's how we compute it but this at the end is going to represent this duplicate minus the missing number and this is going to be that second equation where we actually have duplicate squared minus missing squar so I now realize that there's one part in the drawing explanation I didn't show you and that's what's going to allow us to actually compute the missing and duplicate number in general we kind of did it when we actually had real numbers like instead of X and Y I think we had -1 and5 but if we want to have the formula where we kind of use the variables uh let's quickly do that so we were able to do this with an example where we actually had like numbers1 and neg5 what about the general case where this is X and this is y we're going to do the exact same thing I did earlier with the substitution so here we solve for D we get D is equal to x + m we take D we substitute it here we'll get x^2 + m^2 + 2 m for that D2 term and then we'll have Min - m^2 which is equal to Y so same thing here rid of this and rid of this and now we just want to solve for M we get 2 m = to Y subtract x^2 and then divide the whole thing by two and you get m is equal to this perfect that's good because we've already solved for D so we pretty much have both equations so this is what I'm going to plug in okay back to the code here now we know we put y - x^2 like this and then divide that by 2 * x with the duplicate it's a lot easier because we can kind of just look at what we have up above it's going to be equal to the missing number that we have now computed plus X and then we can turn them just like this okay last thing to do actually compute this formula and this formula we can do that with a single Loop so we'll go for I in range from one all the way up until n and to compute this it's pretty easy we just take every number from nums and add it to X and we take every number from the range from 1 through n and we subtract that or in other words you could rearrange this formula to be this like move the negative I up above and there is one little bug here we're going to get an index out of bounds error because we're iterating from 1 to n+ one so we should put a minus one over here the order you actually do the addition doesn't really matter obviously but this is what we're doing this is like that big addition I was doing at the beginning of the explanation now we can do the same thing with Y it's going to be the exact same thing except each of these is going to be squared so this squared subtract Ed by this squared okay that's the whole code it looks like magic but it isn't and I'll run it to prove it to you as you can see on the left it works thank you so much for watching if you found this helpful please check out NE code. thanks for watching and I'll see you soon