In this guide, you will get 948. Bag of Tokens LeetCode Solution with the best time and space complexity. The solution to Bag of Tokens problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.
Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):
Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.
Return the maximum possible score you can achieve after playing any number of tokens.
Example 1:
Input: tokens = [100], power = 50
Output: 0
Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).
Input: tokens = [200,100], power = 150
Output: 1
Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.
There is no need to play token0, since you cannot play it face-up to add to your score. The maximum score achievable is 1.
Example 3:
Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
Play token2 (300) face-up, reducing power to 0 and increasing score to 2.
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
int ans = 0;
int score = 0;
int i = 0; // the index of the smallest token
int j = tokens.size() - 1; // the index of the largest token
ranges::sort(tokens);
while (i <= j && (power >= tokens[i] || score)) {
while (i <= j && power >= tokens[i]) {
// Play the smallest face up.
power -= tokens[i++];
++score;
}
ans = max(ans, score);
if (i <= j && score) {
// Play the largest face down.
power += tokens[j--];
--score;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
948. Bag of Tokens LeetCode Solution in Java
class Solution {
public int bagOfTokensScore(int[] tokens, int power) {
int ans = 0;
int score = 0;
int i = 0; // the index of the smallest token
int j = tokens.length - 1; // the index of the largest token
Arrays.sort(tokens);
while (i <= j && (power >= tokens[i] || score > 0)) {
while (i <= j && power >= tokens[i]) {
// Play the smallest face up.
power -= tokens[i++];
++score;
}
ans = Math.max(ans, score);
if (i <= j && score > 0) {
// Play the largest face down.
power += tokens[j--];
--score;
}
}
return ans;
}
} // code provided by PROGIEZ
948. Bag of Tokens LeetCode Solution in Python
class Solution:
def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
ans = 0
score = 0
q = collections.deque(sorted(tokens))
while q and (power >= q[0] or score):
while q and power >= q[0]:
# Play the smallest face up.
power -= q.popleft()
score += 1
ans = max(ans, score)
if q and score:
# Play the largest face down.
power += q.pop()
score -= 1
return ans # code by PROGIEZ
