LeetCode 948: Bag of Tokens

A clear explanation of solving Bag of Tokens using sorting, greedy choices, and two pointers.

leetcodearraygreedysortingtwo-pointers

Problem Restatement

We are given an array of token values:

tokens

and an initial amount of power:

power

We start with score 0.

Each token may be played at most once, in one of two ways:

Play type Requirement Effect
Face-up power >= token Lose token power, gain 1 score
Face-down score >= 1 Gain token power, lose 1 score

We may play any number of tokens in any order.

Return the maximum score we can achieve. The official statement defines the same face-up and face-down operations and asks for the maximum possible score.

Input and Output

Item Meaning
Input tokens, an integer array
Input Initial integer power
Output Maximum score possible
Token rule Each token can be used at most once
Starting score 0

Function shape:

class Solution:
    def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
        ...

Examples

Example 1:

tokens = [100]
power = 50

We cannot play the token face-up because 50 < 100.

We also cannot play it face-down because score is 0.

Answer:

0

Example 2:

tokens = [200, 100]
power = 150

Play token 100 face-up:

power = 50
score = 1

The maximum score is:

1

Example 3:

tokens = [100, 200, 300, 400]
power = 200

One optimal sequence is:

play 100 face-up   -> power = 100, score = 1
play 400 face-down -> power = 500, score = 0
play 200 face-up   -> power = 300, score = 1
play 300 face-up   -> power = 0,   score = 2

Answer:

2

These are the standard examples for the problem.

First Thought

We can try every possible order of playing tokens.

For each token, we may play it face-up, face-down, or skip it.

That creates many possibilities and is not practical.

The choice should be guided by value:

  • To gain score, spend as little power as possible.
  • To regain power, receive as much power as possible.

This suggests sorting the tokens.

Key Insight

Sort the tokens.

Use two pointers:

Pointer Meaning
left Smallest unused token
right Largest unused token

When we can gain score, we should play the smallest token face-up.

This gives 1 score for the lowest power cost.

When we cannot gain score but have at least 1 score, we should play the largest token face-down.

This gives the most power back for one score point.

We also track the highest score ever reached, because playing a token face-down may reduce the current score later.

Algorithm

Sort tokens.

Initialize:

left = 0
right = len(tokens) - 1
score = 0
best = 0

While left <= right:

  1. If we have enough power for the smallest token:

    • play it face-up
    • increase score
    • update best
    • move left

  2. Otherwise, if we have at least one score:

    • play the largest token face-down
    • decrease score
    • increase power
    • move right

  3. Otherwise:

    • stop

Return best.

Walkthrough

Use:

tokens = [100, 200, 300, 400]
power = 200

After sorting:

[100, 200, 300, 400]
Action Power Score Best
Start 200 0 0
Play 100 face-up 100 1 1
Play 400 face-down 500 0 1
Play 200 face-up 300 1 1
Play 300 face-up 0 2 2

The maximum score reached is:

2

Correctness

When playing a token face-up, every unused token gives exactly 1 score. To preserve as much power as possible for future plays, the best choice is the smallest unused token. Any larger face-up token would give the same score while spending more power.

When playing a token face-down, every unused token costs exactly 1 score. To regain as much power as possible, the best choice is the largest unused token. Any smaller face-down token would give less power for the same score cost.

The algorithm applies these two optimal local choices whenever each action is needed.

If the smallest token cannot be played face-up and the current score is 0, no token can be played face-up, and no token can be played face-down. So no further move is possible.

If the smallest token cannot be played face-up but score is positive, playing the largest token face-down gives the maximum possible power increase and is the best chance to unlock future face-up plays.

The algorithm records the maximum score reached at every point. Since face-down moves may temporarily lower score to enable later gains, the final current score may be lower than the best score achieved.

Therefore, the returned best is the maximum score obtainable.

Complexity

Let:

n = len(tokens)
Metric Value Why
Time O(n log n) Sorting dominates
Space O(1) or O(n) Depends on sorting implementation

The two-pointer scan is O(n) because each token is used at most once.

Implementation

class Solution:
    def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
        tokens.sort()

        left = 0
        right = len(tokens) - 1

        score = 0
        best = 0

        while left <= right:
            if power >= tokens[left]:
                power -= tokens[left]
                score += 1
                best = max(best, score)
                left += 1
            elif score > 0:
                power += tokens[right]
                score -= 1
                right -= 1
            else:
                break

        return best

Code Explanation

Sort the tokens first:

tokens.sort()

The smallest unused token is at left.

The largest unused token is at right.

If we can afford the smallest token:

if power >= tokens[left]:

we play it face-up:

power -= tokens[left]
score += 1
best = max(best, score)
left += 1

If we cannot gain score but have score to spend:

elif score > 0:

we play the largest token face-down:

power += tokens[right]
score -= 1
right -= 1

If neither action is possible, the process stops:

else:
    break

Testing

def run_tests():
    s = Solution()

    assert s.bagOfTokensScore([100], 50) == 0
    assert s.bagOfTokensScore([200, 100], 150) == 1
    assert s.bagOfTokensScore([100, 200, 300, 400], 200) == 2

    assert s.bagOfTokensScore([], 100) == 0
    assert s.bagOfTokensScore([100, 200], 300) == 2
    assert s.bagOfTokensScore([100, 200, 300], 150) == 1
    assert s.bagOfTokensScore([25, 100, 500], 25) == 1

    print("all tests passed")

run_tests()
Test Why
[100], power 50 Cannot play anything
[200,100], power 150 One face-up play
[100,200,300,400], power 200 Needs face-down trade
Empty tokens No score possible
Enough power for all Play all face-up
Limited power Best score stays 1
Small then large token Checks greedy face-up first