Successful Pairs of Spells and Potions - Leetcode 2300 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem successful pairs of spells and potions they give us a nice little story but I always try to ignore those so we're basically given two arrays one array is of spells so maybe something like this and another array potions maybe something like this and they're both positive array so we won't have any zeros or negative values in these arrays which is good because what we're trying to do here is get some value from spells well basically for every single value in spells we want to know can we take one of these potions maybe two and multiply it with the spell value so five times two and will this result in this case which is 10 be less than or rather greater than or equal to the success value and this success value is a parameter it's a single integer value it's never going to change so in this example problem which we have pretty much copied the success value the threshold is seven so in this case 10 is greater than or equal to seven so we do have a past that threshold but we're not just looking for a spell and mapping it to a single potion we want to know how many potions can we get such that we satisfy this condition so in this case the trivial way to solve this problem is basically to go through every single spell and then for each of them just cycle through all of the potions and check for each one do we satisfy that condition where the spell value multiplied the potion is going to be less than or rather greater than or equal to success and of course if we do this for every single value in spells the overall time complexity is going to be n where let's say n is the size of spells and M where m is size of potion so we're gonna have to iterate through both of of them with like a nested for Loop so this is going to be the time complexity now is there a way that we can do better and if you've never seen this trick before you might think we can't or you might struggle to come up with an approach but I've seen this pattern before so I know how to tackle it pretty much immediately and this first example is actually pretty good because they give us a sordid potions array which kind of further hints to you how to solve this problem we can take our potions array and it's not necessarily going to be sorted it is in this first example but there are other examples where this array is not necessarily sorted but that doesn't matter we can choose to sort this array yes the time complexity will be M log M because m is the size of the potions array but this is still better than n times M with the nested for loops and this is actually a lot better even though it doesn't quite look like it that's not all though once we're done with that what we want to do is find how many of the potions will work with the spell why are we sorting this in the first place well when we immediately saw that 2 does in fact work do we really need to check any of the values to the right of two because remember this array is sorted why should we check greater values here if 2 times 5 is greater than 7 then every value to the right over here which is greater than or equal to 2 is also going to result in a product that is greater than or equal to seven so there's no point in checking the values here that's the trick that we use to get this to become a binary search problem because binary search is a pretty standard algorithm where we have two pointers left and right pointer we calculate the mid pointer by just taking the halfway point quite pretty easy to do we check an arbitrary value like three how do we check it though how do we know if this is valid well basically five times three is greater than or equal to seven yes it is so three works so basically that tells us we don't need to check any of these two values to the right it's not to say that these aren't valid we know that now all three of these values will work with five but we're crossing these out because we don't have to check them anymore we're now going to start doing our binary search on the left side so I'm going to update these pointers as well I'm gonna cross this out because we don't need to check it either so we take now our right pointer and set it to Mid minus one over here so right is now going to be over here we're going to basically do the same thing get the mid from these two I believe it's going to be this one and what we're going to find is one times five is not greater than or equal to seven so now we found a value that does not work we're still going to cross it out because we're not going to check this value anymore but what we're looking for is the point basically the smallest value that will work we're basically looking for like the intersection or kind of that pivot point where everything to the right over here these will work these potions will work with this spell but everything over here will not that's what we're trying to do and this actually is the point and at this point what our binary search would do is say okay this is the middle now we're going to check does this work it does so we basically segregate the values these ones don't work these ones do how many are over here well we can count that without having to look at every single one we can count it just by taking this last index that does work and basically taking the length and subtracting this value because we know arrays are zero Index this starts at zero this is one so when we take the length of the array we get five we now want to subtract all the values to the left side of this line there's just a single one over here and since this is a zero indexed array if the mid value is one we know there's one value to the left of it if the mid value is 2 we know that there's two values to the left of it so just basic math here now we know how to get the count for each value for each spell now we know how to get the count of the potions once we can do that all we really have to do is build the output array which is basically to take every value here and map it to some value in the output which well the value itself is going to be the count so 4 for this guy and how many values will work for one well we would run the binary search again and what we'd find is that none of these values even the maximum value 5 times 1 is going to be greater than or equal to seven so we'd get a zero for one and for three I'm just going to look at the solution here looks like we get three the reason reason probably is because these three multiplied with three are greater than seven but these two are less than seven when you multiply them so that's the result what about the time complexity well there's two main factors here one we know we had to sort this array at the beginning we said the length is M so the time complexity of that is going to be M log M but there's another thing here for every single one of these guys we're running a binary search on this array to run binary search on an array is just log M where m is the size of that array how many times are we doing it for each value in the Spells array there are n of those so we say the overall time complexity is n Times log M plus M Times log M or you could even kind of do some cool well not super cool but interesting math like this but that's not really too important but with all that said let's go ahead and code this up now so to code this we know the first thing we want to do is sort the potions array so in Python you can do that pretty easily and before now we start actually going through every single spells in the input array and then doing like our binary search here we want to actually declare our results as well it's initially just going to be an empty array but we know that's what we're ultimately trying to return here so I'm just going to put that there immediately so now we know what we're doing here here we're running that binary search what's the template for binary search well you have two pointers left is going to be all the way at the left and right is going to be all the way at the right which is the length of uh what are we running it on potions so the length of potions minus one and how we're going to do it is have a left pointer which is going to be less than or equal to the right pointer if that's not the case that means left cross the right and that means we stop our binary search but remember what we're trying to do with this binary search it's a little bit different than like a standard binary search so I'll try to walk through it we know we are going to need the middle index so that's pretty easy left plus right divided by two even though this can possibly overflow usually for coding interviews it doesn't matter and a lot of my other videos I kind of show you how to write this without having it overflow but I'll skip that for now next we want to check the conditions what is the condition in this case well this particular spell we already have that with s right this particular spell multiplied by some potion which potion at which index well remember that's why we're running binary search our mid index we want the potion from that index is this value greater than or equal to that success parameter that was passed to us if it is then this is valid else it's not valid what about the third case though what about if this is actually equal to success it's exactly equal usually in binary search we immediately stop in that case but here we actually don't want to do that because think of a case like this where our spell is maybe five and our potions array looks something like this one two two two and maybe four and our success value is actually exactly equal to 10. then to start our binary search what we would do is say five times the mid value here let's say this is the mid value so we'd say five times two is ten it's exactly equal to the success threshold so does that mean that we're done with our binary search no because even though we found this value it's actually not the leftmost value we want this guy over here not the one but this two so since we could possibly have duplicates like this that's why I'm going to be writing the binary search as follows I'm going to say if we get to a point like this for example over here we now want to start searching to the left we can do that by taking our right pointer and setting it to Mid minus one but we also want to save this index we want to save it in a variable let's say which is initially going to be called index what this should do is find the weakest position or rather weakest potion that works and when we say weakest we mean furthest to the left so with this variation that will work well once we add this line here index is equal to the mid value if it was valid and then we go further to the left we just keep going as far to the left as we possibly can until maybe we encounter an invalid value and then we would try shifting to the right a bit or maybe we would just stop when we do encounter an invalid value we just need to update the left pointer to be mid plus one we're going to start searching to the right side now you can probably see here I haven't initialized the index yet let's initialize it to zero but I'm going to change that in just a second and I'll show you why after we are done with this binary search we now have the value that we're looking for it's stored in Index this will actually be accessible outside of the while loop the way that python works but I will just for clarity copy and paste it up here so that this will be easy to translate into other languages as well but now we just want to take that index that we calculated and add it to the result well not quite we want to add the amount of valid values we can use this index to count that so we're going to take the length of positions and subtract from it the index value which tells us how many values are to the left of it so this is basically the calculation I talked about in the drawing explanation it's pretty simple it gives us the number of valid potions that will work now there's just one problem here the initial value that we set is zero what happens if we never found any valid potions what would this end up doing well this would never reassign the index if we never execute this if statement if we always go with this one we'll never execute this that means index will stay zero that means if we don't find any potions that work the value we're going to append here is the length minus zero which is going to be too high what we would want to append here is zero how do we do that well by initializing the index value to length of position so now if we never reassign this we'll end up getting length of positions minus length of positions which will be zero which is exactly what we would want to append in that case so now let's go ahead and run this code to make sure that it works okay I got everything right except the variable name I don't know how I even messed that up but let's go ahead and change it to potions not positions and it looks like the syntax highlighting on leak code is going a bit crazy but I think this code will still work and as you can see it does it's pretty efficient though there is a pretty comparable solution I think that's how some people are getting a better run time even though the overall Big O time complexity is the same if you found this helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon