Bag of Tokens — Medium Problem & Solution

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)…

Difficulty: Medium
Topics: Arrays, Greedy, Sorting, 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 <= 1000
0 <= tokens[i], power <= 10000

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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue