Watch 10 video solutions for Bag of Tokens, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by codestorywithMIK has 41,656 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |