LeetCode 948: Bag of Tokens

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:

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

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:

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]

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)

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