Bag of Tokens - Leetcode 948 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem bag of tokens so this is basically a little game and the rules are pretty simple so there are two concepts one is known as the score and another is known as the power initially the score is going to be zero and initially the power is going to be given to us as a parameter so in this first example you can see that the power is 50 we're also given a list of tokens suppose that the list is 100 and 200 actually to make it more interesting let's change it to this now for every single token that we have for us to be able to play a token we can do so in two different ways and it's going to be related to how these things work as well so we can play any of these tokens face up if we want to play it face up though it's going to cost us this much power or basically if this token is 50 it's going to cost us 50 power if the token is 100 it's going to cost us 100 power but we don't have that much power so therefore we can't play this token at least not right now we also have another choice of playing any of the tokens face down it won't cost us any power but it will cost us some score so I didn't mention earlier but when we play a token face up we actually gain one score but when we play a token face down we actually lose one score but when we play a token face down instead of costing us power we actually gain power so if we decided to play this token face down we'd gain 100 power but we would lose one score now we can only play a token face down if we have enough score if we have at least one score to basically give now if we have zero score which is what we initially start with we can't play anything face down ultimately what we're trying to do here is maximize the score itself and then return whatever Max value we can get for that so basically everything that we've talked about boils down to wanting to play certain tokens face down which it's going to cost us some score sure so like it'll cost us one score but it will increase our power to the point that we can play multiple tokens so let's just go through this example we have 50 power we can play this token so now our score will go to one our power is going to be down to zero so if we want to play another token we can't and of course which ones would we want to play well for the record when we played this one we played it face up among the other tokens to play we probably want to play the smaller ones face up we don't have any power so we can't play them face up we want to play one of these tokens face down probably we want to play the biggest token face down because it's going to cost us one score regardless but this one is going to give us 100 power whereas playing playing this one face down would only give us 50 power we want more power so we can play more tokens and maximize the score so we decide to play this one face down we lose a score so our score is down to zero but our power is going to be 100 now now we can play this token and play this token and then our score will be two our power will be down to zero but this is the way to maximize the score so the max score that we were ever able to create is two the algorithm for what I just did is actually very simple we kind of want to be greedy don't we we want to play the smallest tokens face up but we want to play the biggest tokens face down how can we arrange the input such that it's easy for us to get both those well we can basically sort the tokens and then use a two-pointer Technique One pointer over here will be the smallest values and a second pointer over here will be the biggest values so this is basically a greedy solution usually the hardest thing with greedy Solutions is just confirming that they work like this solution might seem too simple to you at first I think it probably make sense to you that we want to play the smallest tokens face up I think that much probably makes sense like if we have a choice any token is going to give us the same exact amount of score so if we have a choice play the ones with a smaller value it'll cost us less power and similarly when it comes to playing bigger tokens we want to play those face down cuz then we gain more power and it costs us the same exact amount of score so intuitively it makes sense the question is like what if I had an extra 100 in here so suppose there's a second 100 over here well let's say it costs us 50 power to play this token and then we have one score zero power then we play this one face down so then we're back to zero score but we have 100 power now then we play these two now we're at two score zero power and now we have enough like with our two-pointer Technique we still have some tokens to play this is the last one though and when we play it it's going to bring our score down to one it's going to give us a power of 100 now if we had more tokens to play we might be able to maximize our score we might be able to bring it back to two or maybe even higher than two but right now it ends at one so should we return one is one the result no because what we're going to do is keep track of what's the largest score that we could have possibly made at one point the score was two we could have decided to stop playing at that point we don't have to play every single token that we're given so that's kind of why this approach works it will find the maximal possible score even if it continues the simulation because we have no way of knowing if we can actually find a larger score until we continue to play as long as there are tokens left we will continue to play all tokens the overall time complexity of this approach is well the two-pointer solution is Big O of n but we do have to sort the input so that's going to be n log n where we're sorting the tokens now let's code it up so I'm going to initialize the result at the same time that I initialize the score variable and they're both going to be set to zero initially then I'm just going to sort the tokens input array and then we are going to start with our two pointer solution so left and right are going to be the pointers left is going to be set to zero right is going to be the length of the input minus one and then we're just going to continue while the pointers have not crossed each other ultimately trying to do is return the result the max possible score then we're going to check a couple things the first one is of course we want to play the token face up if we can so let's check is the power that we have greater than or equal to the cost of playing the smallest token the smallest token we can find with the left pointer and so this is the cost of that token if we have enough power to play it let's go ahead and play it what does that mean well we're going to lose this much power power so whatever value it had we lose that much we're going to shift our left pointer by one we're going to increment the score by one as well and to maximize the score just to keep track of what the max possible score ever was we can just take result and set it to Max of itself and whatever score we computed this is what we want to do if we can do it now if we can't do that we just don't have enough power let's try playing a card face down and we can only do that if our score is at least one so let's just check that the score is greater than zero so if that's the case we will take the token with the largest value and play it playing that entails decrementing our power by that same amount then taking our right pointer and shifting it to the left and decrementing our score by one as well now I'm not checking that the result is a new maximal here because if we're decrementing the score it's definitely not going to be a new Max so these are the two main cases now there is a third case if you don't want to get stuck in an infinite Loop what happens if we don't have enough power to play a token but we also have a score of zero so we can't play any of the tokens face down well at that point we should probably just return so we should just return whatever result we got because we can't do anything anymore or we can just break out of the loop and then end up returning down here anyway so that's what I'm going to do this is the entire code let's run it to make sure that it works and I had a unfortunate typo so when we play a token face down we want to add to the power cuz that's the whole point of playing a token face down we're losing score but gaining power here we're losing power but gaining score so sorry about that as you can see on the left though the code does work it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon