Bag of Tokens — Solution in Python, Java & C++
Bag of Tokens solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and sorting.
Bag of Tokens is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Two Pointers
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You start with power energy and a score of 0. Each token may be played once, face up or face down:
- face up: spend
tokens[i]energy (you must have enough) and gain 1 score; - face down: gain
tokens[i]energy and lose 1 score (you must have at least 1 score).
Return the maximum score reachable.
Example 1
Input: tokens = [100], power = 50
Output: 0
Explanation: Not enough energy to play the only token face up.
Example 2
Input: tokens = [200,100], power = 150
Output: 1
Explanation: Play 100 face up; the remaining 50 energy cannot buy 200.
Example 3
Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play 100 up, 400 down, then 200 and 300 up.
Constraints
0 <= tokens.length <= 10000 <= tokens[i], power <= 10000
Hints for Bag of Tokens
Hint 1
Sort the tokens: spend energy on the cheapest and sell the most expensive.
Hint 2
Two pointers — take from the front face up while you can afford it, otherwise sell from the back.
Hint 3
Track the best score seen, since selling temporarily lowers the current score.
How to solve Bag of Tokens
Buying score should always be as cheap as possible and selling score as lucrative as possible, which after sorting means taking from the front and the back respectively.
Approach
- Sort the tokens ascending.
- While the pointers have not crossed: if the current energy covers the cheapest remaining token, play it face up, spending energy and gaining score.
- Otherwise, if the score is positive, play the most expensive remaining token face down, gaining energy and losing score.
- If neither move is possible, stop. Track the maximum score seen along the way.
Why it works
Exchange argument: replacing a face-up token by a cheaper unused one never costs more energy, and replacing a face-down token by a more expensive unused one never yields less. So the extremes are always safe choices. Recording the running maximum matters because a sell step lowers the score in the hope of buying two later.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Returning the final score rather than the best seen underreports whenever the last move was a sell.
- Selling with a score of 0 is illegal and would loop forever.
- An empty token list scores 0.
Reference solution
Python
from typing import List
def bagOfTokensScore(tokens: List[int], power: int) -> int:
s = sorted(tokens)
lo, hi = 0, len(s) - 1
score = best = 0
while lo <= hi:
if power >= s[lo]:
power -= s[lo]
lo += 1
score += 1
best = max(best, score)
elif score > 0:
power += s[hi]
hi -= 1
score -= 1
else:
break
return bestJava
public static int bagOfTokensScore(int[] tokens, int power) {
int[] s = tokens.clone();
Arrays.sort(s);
int lo = 0, hi = s.length - 1, score = 0, best = 0;
while (lo <= hi) {
if (power >= s[lo]) {
power -= s[lo];
lo++;
score++;
best = Math.max(best, score);
} else if (score > 0) {
power += s[hi];
hi--;
score--;
} else break;
}
return best;
}C++
int bagOfTokensScore(vector<int>& tokens, int power) {
vector<int> s = tokens;
sort(s.begin(), s.end());
int lo = 0, hi = (int) s.size() - 1, score = 0, best = 0;
while (lo <= hi) {
if (power >= s[lo]) {
power -= s[lo];
lo++;
score++;
best = max(best, score);
} else if (score > 0) {
power += s[hi];
hi--;
score--;
} else break;
}
return best;
}JavaScript
var bagOfTokensScore = function(tokens, power) {
var s = tokens.slice().sort(function(a, b) { return a - b; });
var lo = 0, hi = s.length - 1, score = 0, best = 0, p = power;
while (lo <= hi) {
if (p >= s[lo]) {
p -= s[lo];
lo++;
score++;
if (score > best) best = score;
} else if (score > 0) {
p += s[hi];
hi--;
score--;
} else break;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms