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):
tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.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).
Example 2:
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:
100) face-up, reducing power to 100 and increasing score to 1.400) face-down, increasing power to 500 and reducing score to 0.200) face-up, reducing power to 300 and increasing score to 1.300) face-up, reducing power to 0 and increasing score to 2.The maximum score achievable is 2.
Constraints:
0 <= tokens.length <= 10000 <= tokens[i], power < 104This approach involves using a two-pointer technique to process the tokens. By sorting the tokens array, we aim to utilize the smallest possible tokens first to maximize score when power allows, and then balance power by utilizing score if achievable.
Start by sorting the tokens array. Maintain two pointers: one at the start to play face-up when you have enough power, and the other at the end to play face-down when a score can be sacrificed to gain more power. Keep track of the current score and maximum score achieved. This greedy approach helps in maximizing score by trying to play as many tokens face-up as possible while being able to trade score for power when needed.
The implementation begins by sorting the tokens array using qsort. Two pointers, left and right, are initialized to keep track of which tokens to consider for playing face-up or face-down. If the power is enough to play the token at the left pointer face-up, the player does so and increments the score. Otherwise, if the score allows it, the player can play the token at the right pointer face-down to increase power. The loop continues until no more moves are possible. The maximum score obtained is returned.
C++
Java
Python
C#
JavaScript
The time complexity is O(n log n) due to sorting the tokens array. The space complexity is O(1) as no additional space besides variables is used.
In the dynamic programming approach, we consider decisions at each token in terms of playing face-up or face-down, and store results for subproblems to optimize the score obtained.
The dynamic programming table, dp[i][j], keeps track of the maximum score achievable with the first i tokens and with j power. For each token, either spend or gain power while adjusting the score, and calculate the best possible outcome for each state.
This C implementation uses a DP table to track the best scores possible at each state. As the array updates for each token processed, it compares the outcomes of playing the token face-up or face-down. The final answer is at dp[tokensSize][power], representing the maximum score achievable for the given number of tokens and initial power.
C++
Java
Python
C#
JavaScript
The time complexity is O(n * m) where n is the number of tokens and m is the initial power range explored. The space complexity is also O(n * m) due to the DP table usage.
| Approach | Complexity |
|---|---|
| Greedy Two-Pointer Technique | The time complexity is |
| Dynamic Programming Approach | The time complexity is |
Bag of Tokens | Greedy Explanation | Google | Leetcode 948 • codestorywithMIK • 21,309 views views
Watch 9 more video solutions →Practice Bag of Tokens with our built-in code editor and test cases.
Practice on FleetCode