Leetcode Daily | 12–09–22 | Bag Of Tokens
So from today onwards I have decided to post this blog for the Leetcode daily challenge with its explanation from brute force to optimized one. Since many people face problems while understanding the code, I decided to give a proper explanation for every statement in the code.
Here is the question that we will be looking at today.
You have an initial power of
power, an initial score of
0, and a bag of
tokens[i] is the value of the
ith token (0-indexed).
Your goal is to maximize your total score by potentially playing each token in one of two ways:
- If your current power is at least
tokens[i], you may play the
ithtoken face up, losing
tokens[i]power and gaining
- If your current score is at least
1, you may play the
ithtoken face down, gaining
tokens[i]power and losing
Each token may be played at most once and in any order. You do not have to play all the tokens.
Return the largest possible score you can achieve after playing any number of tokens.
0 <= tokens.length <= 1000
0 <= tokens[i], power < 104
You can find the link to the question here, https://leetcode.com/problems/bag-of-tokens/
For the first approach, we will use two pointers and greedy method. This can only be applied to the array if it is sorted in acending order.
We will place on pointer at the staring and another one at the end. After that, we will teaversing the array till the starting pointer becomes equal to the ending pointer. While traversing, we will keep a track of elements.
If the element is greater than the power, we will look the score and gain the power. Else, if the element is less than the power, we will gain a score and loose the power.
Here is the algorithm that we will be using in this code-
- sort the token in increasing order
- create two pointer i, j, where
i = 0, j = n; initially
0 <= x <= irepresent the tokens face up i.e, [Score ⬆, Power ⬇]
j <= x <= nrepresent the tokens face down i.e, [Score ⬇, Power⬆]
- if we have sufficient power to face up ith token, power — token[i], i++.
- else if we have some score
[i - (n - j)]face down jth token,
j--, power + token[j].
i - (n - j) represents the score since (face up - face down) = score, face up = i and face down = n - j
we also need to check if we face down j we should have some unplayed token to face up. That's why we are checking j > i + 1
- if we have no move to make break the loop.
The time complexity of the above code is O(nlogn) and the space complexity is O(1).