Divide Players Into Teams of Equal Skill - Leetcode 2491 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem divide players into teams of equal skill so a nice little cozy problem for us to solve today so we're given a set of numbers each of these corresponds to a person's skill level we want to partition this into groups of two they can be chosen however we want so like they don't have to be adjacent I could have chosen a group of two to look like this and however else we want to but every single group of two has to have the same sum not the two individual elements need to be equal but the sum of this and this and this have to be the same so right now this is five this is six and this is seven clearly they are not the same if we put both of the threes in a group and then the two and the four and then these two then each of them will have a sum of six and that does work then they'll all have the same sum now if it's not possible for us to do that we want to return -1 as like the default value but if it is possible for us to do that and we looked at one possible way which is this I just colorcoded it to make it obvious but we would go through every group so the green group and take the two numbers and then multiply them together 3 * 3 same thing with this group 5 * 1 and then this purple group is going to be 2 * 4 and then with all of these we're going to add them up and then this is the return value now the first question you might wonder is well what if there are multiple Solutions what do we do in that case well I'm going to show you that there can't possibly be multiple Solutions and once I show you that you'll probably know how to solve the problem pretty easily the main requirement is that each group sums up to the same thing so let's say we have n elements in this case n is equal to 6 so therefore we're going to have this divided by two this many groups we're going to have three groups so if I told you that every element in the input is going to be a positive integer can you now tell me how much each group needs to have what value does it need to have well all you do is take the total of the entire thing which is 18 and divide it by the number of groups so we're going to get six for every group it has to be like that it has to have six in every single group so now we know that much we know what we're looking for now if we go through each element one valid way to solve this problem is kind of like two sum two or container with most water I think two some two is probably uh the more similar problem though so if you are looking for one I would check that problem out I have a video for it but if we took all of the elements and sorted them we'd get something like this 1 2 3 3 4 5 we could then do a two pointer approach for each element we map it to the element on the other side and the reason we do this is because if there is a valid solution the smallest element must be mapped to the largest element like we would not ever map this to the second largest element because then what are we going to group this guy with something even bigger if that's the case then this pair automatically is going to have a sum larger than the other one so we'd kind of follow a two-pointer approach and we'd keep Shifting the elements and we could keep verifying that the sums are equal to what we expect if they're not at that point we would return Nega 1 this is a valid approach but due to sorting it's going to be n log n and then like the two-pointer approach is going to be the linear part but this is the bottleneck we can actually do this problem without sorting ilar to how you solve two sum the regular way just by using a hashmap to store the diff because as I kind of showed if we know for sure that the target which is how much each group is going to have is going to be six we know that for sure then what we can actually do is scan through the input for each element for example three we can just compute the diff this has to be grouped with another three there's no other possible element that this could be grouped with because the target has to be six so only three could be grouped with this we do happen to have another three so we found one valid group great then we go to the next element two the diff is going to be 6 - 2 that's four do we have a four yep we do so kind of cross that out same thing here five we have a one and then we're good if we didn't have a one if we had a two Instead at this point we would have to return negative 1 cuz there isn't a solution so what I did was just by drawing over this array I kind of crossed out elements but in terms of coding it you can't really manipulate an array as you iterate through it at least it's not good to do that so a better approach to this would be to dump all of these into a hash map which I'm going to call count where we take each value map it to the count of that value so we'd have something like this so I've taken each value mapped it to the count and then we could still iterate over the input array at least that's how I'm going to do it I'm going to see there's a three here okay the count of three is non zero I'm going to compute the diff of it so I'm going to start by Computing the total sum of the input and I'm just going to use the built-in sum function in Python and then I want to know if we can even divide this into enough groups so what I would say is take the total and then mod it by the length of the input divided by two this will work I'm pretty sure but I just kind of prefer to have multiplication instead so if I multiply this by two and this by two we'll actually get something like this and then we don't need to do division but that doesn't really matter that's a very small thing so if this is nonzero that means that we can't divide it into that many groups and in which case we don't need to do anything we can just immediately return Nega 1 now if that's not the case we want to count the occurrence of each value in scale now I could create a loop I could create a hashmap and do that but python provides something built in called a counter which will save us a couple lines of code and it'll do exactly that just count the occurrences of each element you can learn more about these little tricks in my python for coding interviews course if you're interested um but at this point we want to compute the result like that product and then we want to return it now how do we get there well we're going to go through every value in the skill array but first let's compute the target value that we're actually looking for so I'm going to compute it like this we take the total and divide it into half this many groups but I'm just going to rewrite that with like multiplication so I'm going to do two times the total and then integer divide that by the length of scale doesn't really matter you can do however you want you could have divided this thing by two first and gotten rid of that but now we're going to go through every skill every integer value now it's possible that the count of this might actually be zero because as we're going through the skills we're going to be doing two at a time you'll see what I mean in just a second so what I'm going to have here is if not this so the count of that is equal to zero then continue because then we don't need to find a matching pair for this element anyways otherwise we need to find a matching pair and to do that we need to get the diff of this element with the target so Target minus s that gives us the diff now we want the count to be non zero but if it is zero if not count of the diff or maybe the diff just doesn't exist in the hashmap at all in that case we can also return NE 1 in either case return negative 1 otherwise we can update our result by adding to it the product of s and the diff the two elements that make up the pair and then we can update the count of each element so incre decrement that by one and decrement uh the diff count by one so this is the entire solution I'll run it you can see it works I do believe it's pretty efficient in terms of Big O N like it is a linear time solution and it is linear space as well depending on the number of possible values skill could have now I'm wondering to be honest here we check the diff that the count of the diff is non zero but what if s and the diff were actually the same element and then we check that the count is non zero that makes me think that we should probably put this line up above we should put that here or at the very least before we check this but for some reason it still passes on leak code the original way that I had it I'm not sure if that's just because we do the verification here or I'm not sure maybe if leak code is just missing a test case let me know if you have any thoughts on that but if you're preparing for coding interviews check out n code. for a lot more thanks for watching and I'll see you soon