Take Gifts From the Richest Pile - Leetcode 2558 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem take gifts from the richest pile the idea is we're given an array of gifts they are going to be integers I guess in this example we have this array with five values they're all positive and I think we can expect that they're all going to be positive or zero we probably can't have a negative number of gifts and speaking of gifts each of these numbers actually represents a pile and the number itself tells us how many gifts are in that pile and every second we are able to perform an operation which includes this we can pick one of these piles the one that has the max number of gifts if there are multiple we can choose any of them so if there is a tie like we have two that have 100 we can choose any and what we want to do with that number is leave behind the floor of the square root what does that mean well we have a 100 so take the square root of it and when you take the square root of a number we might end up with a decimal this time it's going to be 10 but imagine you had uh the square Ro T of 10 then you're going to get something like 3.33 and we want to take the floor of that so we want to round that down we would end up with just 3.0 so just a three that's the number we're going to replace the pile with now after we're done with that specifically after we're done performing this operation exactly k a times which is the second parameter that's given to us they probably could have mentioned that earlier but it's actually for me easier when they actually mention it when you're actually needing that parameter rather than like mentioning it up front but sometimes they do that to intentionally confuse you either way that's the problem how exactly do we go about solving it well so far it seems like a simulation so that's what you might try how could we Brute Force this simulation well find the maximum in an array that's a l time operation and if we have to do it K * the overall time complexity is going to be n * K because every time we're going to have to find the maximum and then replace it with a new value and just keep doing that you might think well can't we just sort the array imagine you have an array like this one 10 20 and maybe 100 you pick the maximum you have to scan through well I guess this time you don't have to scan through because it's sorted so we can just go to the rightmost value and update it by taking the sare root of it it's going to be 10 but now the problem is we modified the array so now it's no longer sorted I mean we could take this value and then insert it somewhere in sorted order but that's going to be a linear time operation in the worst case so actually sorting the array doesn't really make the problem any better but there is a data structure that has a sorted property to it can you think of the data structure that I am thinking of well it's called a heap and specifically in this case we're going to be needing a maximum Heap this data structure is designed to have like a sorted property but also be able to add and remove elements from it dynamically if you're not familiar with heaps that's perfectly okay you're probably a beginner and that's fine I would head over to NE code iio to learn a little bit more about heaps you can probably check out my beginner course or some videos on YouTube about heaps but this is how it's going to work we're going to have the max Heap we're going to throw all of these values into the Heap we're going to run a buil-in method called heapify it can turn all of these elements into a heap in linear time so actually it's faster than sorting so we do that in linear time and then we can run the simulation so K times we're going to take the maximum so this time we're going to take 100 remove it from the Heap so now we have 100 we're going to square root it and floor it and we'll have 10 and then we'll take 10 and add it back to the Heap so we replace the 100 with 10 we'll just keep going like that so now we have 64 I think when you square root that it'll become eight now the biggest is 25 same thing and now we do 10 um and then floor it so it'll be three and then you do I guess we've already done actually four runs of the simulation so now that we are done what we actually want to do is return the number of gifts that are remaining so basically just take all the remaining values and sum them up so whatever's in the max Heap you can just sum up the values so assuming I did this correctly we should have 8 + 9 + 3 that's 20 + 5 and 4 that's 29 so that does look correct so we're pretty much ready to code this up now in terms of the time complexity though pushing and popping from a heap is not linear time it's actually log n time where n is the size of the Heap so we're doing that K times the overall time complexity is going to be K log n not too bad space complexity is going to be Big O of n cuz we're adding all the elements to the Heap one last thing that I want to quickly mention is when we take these values and add them to the Heap we're actually going to make them negative because python unfortunately does not have a Max Heap built in but we can get around that by making all the values negative here's an example real quick if I have 100 here -25 and let's say -64 I'm going to pop from the Heap since this is actually a Min Heap under the hood what's going to happen is we're going to end up popping the smallest value that's negative 100 after we pop it let's take the absolute value of it or just multiply it by1 and that'll make it positive then we'll have positive 100 then we're going to square root it and then take the floor of it which is going to give us 10 and then when we add it back to the Heap we're not going to add positive 10 we're actually going to add a - 10 because we want this to actually act as if it were a Max Heap and by changing all the values to negative we can basically do that so in terms of coding there's actually not much to do first we want to take this array of gifts and turn it into a heap python allows you to do this Heap q. heapy and then pass in the array and it'll turn it into a heap like basically it will leave it as a list because heaps are implemented with arrays under the hood you'd probably know that if you've taken my courses or any courses on heaps but remember we wanted all the values to be negative before we did that so the easiest thing to do in Python is to create a new list just map all these values and turn them negative so something like this let's say or rather let's just replace gifts so this is creating a new list and replacing the gifts variable with it and so I'm going to use list comprehension so I'm going to do this for G in gifts for every gift I'm going to add the negative of it to this list this is called list comprehension if you're not familiar with these python tips and tricks you can check out my python for coding interviews course it literally will show you how to do this Max Heap pattern I'm talking about but after that we just pop K times so for underscore in range K let's go ahead and do Heap Q Heap pop from the gifts Heap we will get a value n it will actually be negative so to turn it into a positive I'm going to add a negative sign here you can do that in Python in most languages you would need to do something like this I think but in Python you can get away with this and so then we want to now push back to the Heap a certain value so back to the gifts Heap we want to push the square root of N and we want to take the floor of it as well so in Python those are some built-in functions we can just use just like that and then after we're done with all of that what we want to do is return the sum of the gifts but don't forget it's very easy to do so we made the gifts negative originally yes we can sum them up pretty easily like this but each of them is going to be negative so we can just take the negative of this we don't really have to for these gifts to all be positive since they're all negative just summing them up and then taking the negative of that should be good enough I almost forgot when you add back to the Heap you want to make the value negative so let's add that one as well and you can see here it works and it's pretty efficient if you found this helpful you might find my python for coding interviews course helpful or some of my other courses as well here is that lesson I was talking about on the heaps so if you go down here how do you do a Max Heap in Python there is this lesson which will literally uh teach you exactly that and it has like a nice little interactive lesson where you can literally practice uh doing that as well see you soon