Bag of Tokens solution and explanation
Google
9 more videos on this problem
Bag of Tokens | Greedy Explanation | Google | Leetcode 948codestorywithMIK · 18:28 · 47K views
Bag of Tokens - Leetcode 948 - PythonNeetCodeIO · 8:51 · 13K views
948. Bag of Tokens | Greedy | 2 Pointers | Complete IntuitionAryan Mittal · 15:24 · 3K views
Bag of Tokens | Live Coding with Explanation | Leetcode #948Algorithms Made Easy · 6:41 · 2K views
Leetcode 948 Bag of Tokens | Tree Traversal | Coding Decoded SDE SheetCoding Decoded · 7:40 · 1K views
Leetcode - Bag of Tokens (Python)Timothy H Chang · 5:37 · 953 views
Bag of Tokens | Leetcode #948Techdose · 14:22 · 830 views
Bag of Tokens | Leetcode 948 | leetcode solutionEasyLeetcode · 9:04 · 552 views
Daily Leetcode #895: Sep 12, 2022 - 948. Bag of TokensProgramming Live with Larry · 9:19 · 379 views
LeetCode 948. Bag of TokensBitVerse · 12:02 · 339 views
The problem
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, losingtokens[i]power and gaining1score. - Face-down: If your current score is at least
1, you may play tokeni, gainingtokens[i]power and losing1score.
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:
- Play token0 (
100) face-up, reducing power to100and increasing score to1. - Play token3 (
400) face-down, increasing power to500and reducing score to0. - Play token1 (
200) face-up, reducing power to300and increasing score to1. - Play token2 (
300) face-up, reducing power to0and increasing score to2.
The maximum score achievable is 2.
Constraints:
0 <= tokens.length <= 10000 <= tokens[i], power < 104
Approach overview
Problem 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 1: Greedy Two-Pointer Technique
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.
def bagOfTokensScore(tokens, power):
tokens.sort()
left, right = 0, len(tokens) - 1
score, maxScore = 0, 0
while left <= right:
if power >= tokens[left]:
power -= tokens[left]
score += 1
left += 1
maxScore = max(maxScore, score)
elif score > 0:
power += tokens[right]
score -= 1
right -= 1
else:
break
return maxScore
print("Maximum Score:", bagOfTokensScore([100, 200, 300, 400], 200))import java.util.Arrays;
class Solution {
public int bagOfTokensScore(int[] tokens, int power) {
Arrays.sort(tokens);
int left = 0, right = tokens.length - 1;
int score = 0, maxScore = 0;
while (left <= right) {
if (power >= tokens[left]) {
power -= tokens[left++];
score++;
maxScore = Math.max(maxScore, score);
} else if (score > 0) {
power += tokens[right--];
score--;
} else {
break;
}
}
return maxScore;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] tokens = {100, 200, 300, 400};
int power = 200;
System.out.println("Maximum Score: " + solution.bagOfTokensScore(tokens, power));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(tokens.begin(), tokens.end());
int left = 0, right = tokens.size() - 1;
int score = 0, maxScore = 0;
while (left <= right) {
if (power >= tokens[left]) {
power -= tokens[left++];
score++;
maxScore = max(maxScore, score);
} else if (score > 0) {
power += tokens[right--];
score--;
} else {
break;
}
}
return maxScore;
}
int main() {
vector<int> tokens = {100, 200, 300, 400};
int power = 200;
int result = bagOfTokensScore(tokens, power);
cout << "Maximum Score: " << result << endl;
return 0;
}function bagOfTokensScore(tokens, power) {
tokens.sort((a, b) => a - b);
let left = 0, right = tokens.length - 1;
let score = 0, maxScore = 0;
while (left <= right) {
if (power >= tokens[left]) {
power -= tokens[left++];
score++;
maxScore = Math.max(maxScore, score);
} else if (score > 0) {
power += tokens[right--];
score--;
} else {
break;
}
}
return maxScore;
}
console.log("Maximum Score:", bagOfTokensScore([100, 200, 300, 400], 200));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int bagOfTokensScore(int* tokens, int tokensSize, int power) {
qsort(tokens, tokensSize, sizeof(int), compare);
int left = 0, right = tokensSize - 1;
int score = 0, maxScore = 0;
while(left <= right) {
if(power >= tokens[left]) {
power -= tokens[left++];
score++;
if(score > maxScore) maxScore = score;
} else if(score > 0) {
power += tokens[right--];
score--;
} else {
break;
}
}
return maxScore;
}
int main() {
int tokens[] = {100, 200, 300, 400};
int power = 200;
int result = bagOfTokensScore(tokens, 4, power);
printf("Maximum Score: %d\n", result);
return 0;
}using System;
public class Solution {
public int BagOfTokensScore(int[] tokens, int power) {
Array.Sort(tokens);
int left = 0, right = tokens.Length - 1;
int score = 0, maxScore = 0;
while (left <= right) {
if (power >= tokens[left]) {
power -= tokens[left++];
score++;
maxScore = Math.Max(maxScore, score);
} else if (score > 0) {
power += tokens[right--];
score--;
} else {
break;
}
}
return maxScore;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] tokens = new int[] {100, 200, 300, 400};
int power = 200;
Console.WriteLine("Maximum Score: " + solution.BagOfTokensScore(tokens, power));
}
}Python's solution sorts the tokens list and uses two pointers to determine the next move. Depending on power and score, tokens are played either face-up or face-down to maximize score. Once possible moves are exhausted, the highest score achieved is returned.
The time complexity is O(n log n), primarily from sorting the tokens. The space complexity is O(1), as we don't use extra space beyond variables.
Approach 2: Dynamic Programming Approach
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.
def bagOfTokensScore(tokens, power):
tokens.sort()
dp = [[0] * (power + 1) for _ in range(len(tokens) + 1)]
for i in range(1, len(tokens) + 1):
for j in range(power + 1):
if j >= tokens[i - 1]:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - tokens[i - 1]] + 1)
if j + tokens[i - 1] <= power and dp[i - 1][j + tokens[i - 1]] > 0:
dp[i][j] = max(dp[i][j], dp[i - 1][j + tokens[i - 1]] - 1)
return dp[len(tokens)][power]
print("Maximum Score:", bagOfTokensScore([100, 200, 300, 400], 200))import java.util.Arrays;
class Solution {
public int bagOfTokensScore(int[] tokens, int power) {
Arrays.sort(tokens);
int[][] dp = new int[tokens.length + 1][power + 1];
for (int i = 1; i <= tokens.length; i++) {
for (int j = 0; j <= power; j++) {
if (j >= tokens[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - tokens[i - 1]] + 1);
} else {
dp[i][j] = dp[i - 1][j];
}
if (j + tokens[i - 1] <= power && dp[i - 1][j + tokens[i - 1]] > 0) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + tokens[i - 1]] - 1);
}
}
}
return dp[tokens.length][power];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] tokens = {100, 200, 300, 400};
int power = 200;
System.out.println("Maximum Score: " + solution.bagOfTokensScore(tokens, power));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(tokens.begin(), tokens.end());
vector<vector<int>> dp(tokens.size() + 1, vector<int>(power + 1, 0));
for (int i = 1; i <= tokens.size(); ++i) {
for (int j = 0; j <= power; ++j) {
if (j >= tokens[i - 1]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - tokens[i - 1]] + 1);
} else {
dp[i][j] = dp[i - 1][j];
}
if (j + tokens[i - 1] <= power && dp[i - 1][j + tokens[i - 1]] > 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j + tokens[i - 1]] - 1);
}
}
}
return dp[tokens.size()][power];
}
int main() {
vector<int> tokens = {100, 200, 300, 400};
int power = 200;
int result = bagOfTokensScore(tokens, power);
cout << "Maximum Score: " << result << endl;
return 0;
}function bagOfTokensScore(tokens, power) {
tokens.sort((a, b) => a - b);
const dp = Array.from({ length: tokens.length + 1 }, () => Array(power + 1).fill(0));
for (let i = 1; i <= tokens.length; i++) {
for (let j = 0; j <= power; j++) {
if (j >= tokens[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - tokens[i - 1]] + 1);
}
if (j + tokens[i - 1] <= power && dp[i - 1][j + tokens[i - 1]] > 0) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + tokens[i - 1]] - 1);
}
}
}
return dp[tokens.length][power];
}
console.log("Maximum Score:", bagOfTokensScore([100, 200, 300, 400], 200));#include <stdio.h>
#include <string.h>
#define MAX_TOKENS 1000
#define MAX_POWER 10000
int max(int a, int b) {
return (a > b) ? a : b;
}
int bagOfTokensScore(int *tokens, int tokensSize, int power) {
int dp[MAX_TOKENS + 1][MAX_POWER + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= tokensSize; ++i) {
for (int j = power; j >= 0; --j) {
if (j >= tokens[i - 1]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - tokens[i - 1]] + 1);
} else {
dp[i][j] = dp[i - 1][j];
}
if (j + tokens[i - 1] <= power && dp[i - 1][j + tokens[i - 1]] > 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j + tokens[i - 1]] - 1);
}
}
}
return dp[tokensSize][power];
}
int main() {
int tokens[] = {100, 200, 300, 400};
int power = 200;
int result = bagOfTokensScore(tokens, 4, power);
printf("Maximum Score: %d\n", result);
return 0;
}using System;
public class Solution {
public int BagOfTokensScore(int[] tokens, int power) {
Array.Sort(tokens);
int n = tokens.Length;
int[,] dp = new int[n + 1, power + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= power; j++) {
if (j >= tokens[i - 1])
dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - tokens[i - 1]] + 1);
if (j + tokens[i - 1] <= power && dp[i - 1, j + tokens[i - 1]] > 0)
dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j + tokens[i - 1]] - 1);
}
}
return dp[n, power];
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] tokens = new int[] {100, 200, 300, 400};
int power = 200;
Console.WriteLine("Maximum Score: " + solution.BagOfTokensScore(tokens, power));
}
}The Python implementation makes use of a 2D list (DP table) to handle scenarios of gaining or spending power for each token processed. Each state computes a maximum score from either face-up or face-down actions, ensuring the highest score possible with the given initial power.
The time complexity here is O(n * m) resulting from state evaluations, and the space complexity remains at O(n * m) due to DP table resource usage.
Approach 3: Greedy + Sorting + Two Pointers
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.
function bagOfTokensScore(tokens: number[], power: number): number {
tokens.sort((a, b) => a - b);
let [i, j] = [0, tokens.length - 1];
let [ans, score] = [0, 0];
while (i <= j) {
if (power >= tokens[i]) {
power -= tokens[i++];
ans = Math.max(ans, ++score);
} else if (score) {
power += tokens[j--];
score--;
} else {
break;
}
}
return ans;
}func bagOfTokensScore(tokens []int, power int) (ans int) {
sort.Ints(tokens)
i, j := 0, len(tokens)-1
score := 0
for i <= j {
if power >= tokens[i] {
power -= tokens[i]
i++
score++
ans = max(ans, score)
} else if score > 0 {
power += tokens[j]
j--
score--
} else {
break
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Two-Pointer Technique | The time complexity is |
| Dynamic Programming Approach | The time complexity here is |
| Greedy + Sorting + Two Pointers | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Bag of Tokens easy or hard?
Bag of Tokens is considered a medium difficulty problem. The implementation is short, but the challenge is recognizing the greedy pattern after sorting and managing the two-pointer decisions correctly.
How to solve Bag of Tokens in O(n)?
A strict O(n) solution is not generally possible because token values must be ordered to make the greedy decisions correctly. Sorting ensures you always spend the least power to gain score and reclaim the most power when needed. The resulting optimal algorithm is O(n log n) time with a linear two-pointer pass.
What is the best approach for Bag of Tokens?
The best approach is a greedy two-pointer strategy. First sort the tokens, then use one pointer for the smallest token and another for the largest. Spend power on the smallest token to gain score, and when power is insufficient but score is available, use the largest token to regain power. This method runs in O(n log n) time due to sorting and O(1) extra space.
What data structure is used in Bag of Tokens?
The core data structure is a sorted array of token values. After sorting, two pointers track the smallest and largest remaining tokens. This enables efficient greedy decisions without additional data structures.
What is the time complexity of Bag of Tokens?
The optimal solution runs in O(n log n) time because the tokens must be sorted first. After sorting, a two-pointer scan processes each token at most once, which takes O(n). Space complexity is O(1) if sorting is done in place.
Bag of Tokens Python or Java solution approach?
Both Python and Java implementations follow the same steps: sort the tokens, maintain two pointers, and track current power and score. When power allows, consume the smallest token to gain score; otherwise, trade a score for power using the largest token. The logic runs in O(n log n) time and constant extra space.
Is Bag of Tokens asked at Google, Amazon, or Meta?
Bag of Tokens is a common medium-level greedy problem frequently used in technical interview preparation. Variants of resource trade-off and greedy ordering appear in interviews at companies like Amazon, Google, and Meta, especially when evaluating algorithmic reasoning with sorting and pointer techniques.