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 < 104Problem Overview: You are given an array of token values and an initial amount of power. Each token can be played face up (spend power to gain score) or face down (spend score to gain power). The goal is to maximize the final score by choosing the right sequence of operations.
Approach 1: Greedy Two-Pointer Technique (O(n log n) time, O(1) space)
The optimal strategy comes from observing that cheap tokens are best used to gain score, while expensive tokens are best used to regain power. Start by sorting the tokens so you can process them from smallest to largest. Use two pointers: left at the smallest token and right at the largest token. If you have enough power, play the left token face up to increase score and move the pointer forward. If you lack power but have at least one score, play the right token face down to regain power and move the pointer backward. Continue until neither move is possible. This greedy decision works because spending the least power for score and reclaiming the most power when necessary keeps future options open. The sort step dominates the complexity at O(n log n), while the two-pointer scan is linear.
This approach combines ideas from Greedy, Two Pointers, and Sorting. The array structure makes operations straightforward since you only move pointers inward without modifying token values.
Approach 2: Dynamic Programming Approach (O(n^2) time, O(n^2) space)
A dynamic programming formulation explores all choices of playing tokens face up or face down while tracking current power and score. After sorting tokens, define a state based on the range of tokens already used and the current score. Transitions simulate either spending power for score or sacrificing score to gain power from a larger token. This captures every valid sequence of operations and guarantees correctness.
However, the state space grows quickly because power changes after every operation. Managing states often requires a 2D table or memoization over token ranges, leading to O(n^2) time and space complexity. The DP approach mainly serves as a conceptual baseline that proves the greedy strategy is safe. In practice, it is slower and harder to implement.
The problem heavily relies on understanding how resource trade-offs behave in a sorted Array. Once tokens are ordered, the smallest token always provides the cheapest score increase and the largest token always yields the biggest power recovery.
Recommended for interviews: The greedy two-pointer solution is what interviewers expect. It shows you recognize the structure created by sorting and can reason about optimal local decisions. Mentioning the DP idea demonstrates deeper understanding, but implementing the O(n log n) greedy approach proves strong problem-solving and optimization skills.
This 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.
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.
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.
There are two ways to use tokens: one is to consume energy to gain points, and the other is to consume points to gain energy. Obviously, we should consume as little energy as possible to gain as many points as possible.
Therefore, we can sort the tokens by the amount of energy they consume, and then use two pointers: one moving from left to right and the other from right to left. In each iteration, we try to consume energy to gain points as much as possible, and then update the maximum score. If the current energy is not enough to consume the current token, we try to consume the current token using points. If the points are not enough to consume the current token, we stop the iteration.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the number of tokens.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Two-Pointer Technique | The time complexity is |
| Dynamic Programming Approach | The time complexity is |
| Greedy + Sorting + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Two-Pointer Technique | O(n log n) | O(1) | Best practical solution. Sort tokens and use two pointers to maximize score efficiently. |
| Dynamic Programming | O(n^2) | O(n^2) | Useful for understanding state transitions and exploring all choices, but slower and rarely needed in practice. |
Bag of Tokens | Greedy Explanation | Google | Leetcode 948 • codestorywithMIK • 41,656 views views
Watch 9 more video solutions →Practice Bag of Tokens with our built-in code editor and test cases.
Practice on FleetCode