LeetCode 948 - Bag of Tokens

The problem gives us a collection of tokens, where each token has a numeric value. We also start with an initial amount of power and an initial score of 0. Every token can be used at most once, and each token can be played in exactly one of two ways.

leetcodemediumarraytwo-pointersgreedysorting

LeetCode Problem 948

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting

Solution

Problem Understanding

The problem gives us a collection of tokens, where each token has a numeric value. We also start with an initial amount of power and an initial score of 0. Every token can be used at most once, and each token can be played in exactly one of two ways.

If we play a token face-up, we spend power equal to the token's value and gain 1 score. This action is only allowed if we currently have enough power to pay the cost.

If we play a token face-down, we gain power equal to the token's value and lose 1 score. This action is only allowed if we currently have at least one score point available.

The objective is to maximize the final score after performing any sequence of valid moves.

In other words, the problem is asking us to carefully trade between two resources:

  • Power, which allows us to buy score
  • Score, which can sometimes be sacrificed to recover power

The input consists of:

  • tokens, an array of non-negative integers
  • power, an integer representing the initial available power

The expected output is a single integer representing the maximum score achievable.

The constraints are important:

  • tokens.length <= 1000
  • tokens[i] < 10^4

Since the number of tokens is relatively small, an O(n log n) solution is completely acceptable. However, exponential exploration of all possible move sequences would become infeasible because each token potentially has multiple choices associated with it.

Several edge cases are important to recognize early:

  • The token list may be empty
  • The initial power may be too small to play any token face-up
  • Tokens may contain zero values
  • We may need to temporarily sacrifice score to gain enough power for future profitable moves
  • Playing a token face-down at the wrong time may reduce the final answer

A correct solution must balance these tradeoffs carefully.

Approaches

Brute Force Approach

A brute-force solution would explore every possible sequence of moves. For each unplayed token, we could decide:

  • Play it face-up, if enough power exists
  • Play it face-down, if score is at least one
  • Skip it entirely

This naturally leads to recursive backtracking or state-space search. At every step, the algorithm would track:

  • Remaining unused tokens
  • Current power
  • Current score

The brute-force approach is correct because it examines all valid move sequences and therefore cannot miss the optimal answer.

However, the number of possible states grows exponentially. Even with pruning, the search space becomes enormous as the number of tokens increases. With up to 1000 tokens, such an approach is completely impractical.

Key Insight for the Optimal Solution

The crucial observation is that not all tokens are equally valuable in each role.

If we want to gain score efficiently, we should spend the smallest possible amount of power. Therefore, when playing face-up, the cheapest available token is always the best choice.

If we need to recover power by sacrificing score, we should gain the largest possible amount of power in return. Therefore, when playing face-down, the most expensive available token is always the best choice.

This naturally suggests sorting the tokens and using a two-pointer strategy:

  • Use the left pointer for the smallest tokens
  • Use the right pointer for the largest tokens

The algorithm greedily buys score as cheaply as possible and only sells score when necessary to unlock more future score gains.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n) O(n) Explores all possible play sequences
Optimal O(n log n) O(1) excluding sort Greedy strategy with sorting and two pointers

Algorithm Walkthrough

  1. Sort the tokens in ascending order.

Sorting is essential because we want quick access to:

  • The cheapest token for face-up plays
  • The most expensive token for face-down plays

After sorting:

  • The left side contains low-cost tokens
  • The right side contains high-value recovery tokens
  1. Initialize two pointers.
  • left = 0
  • right = len(tokens) - 1

The left pointer represents the next cheapest unused token.

The right pointer represents the next most expensive unused token. 3. Track the current score and best score.

We maintain:

  • score, the current active score
  • max_score, the best score achieved so far

We cannot simply return the final score because some sequences temporarily reduce score before later increasing it again. 4. Attempt to play the cheapest token face-up whenever possible.

If power >= tokens[left], we should spend power to gain score because:

  • This is the cheapest available score gain
  • Any more expensive token would cost more power for the same reward

We then:

  • Subtract the token value from power
  • Increase score by one
  • Move left forward
  1. If we cannot afford a face-up play, consider a face-down play.

If:

  • score > 0
  • left < right

then we can sacrifice one score point to gain a large amount of power.

We use the largest remaining token because it gives the maximum possible power recovery.

We then:

  • Add tokens[right] to power
  • Decrease score by one
  • Move right backward
  1. Stop when no further progress is possible.

If:

  • We cannot afford the cheapest token
  • We do not have enough score to trade
  • Or all useful tokens are exhausted

then the process ends. 7. Return the maximum score recorded.

Why it works

The greedy strategy works because every face-up play gives the same reward, exactly one score point. Therefore, we should always minimize the power spent to obtain that reward. Similarly, every face-down play costs exactly one score point, so we should maximize the power gained in return.

Sorting allows us to always make the locally optimal choice, and these local decisions combine into a globally optimal solution.

Python Solution

from typing import List

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

        left = 0
        right = len(tokens) - 1

        score = 0
        max_score = 0

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

        return max_score

The implementation begins by sorting the tokens so that the cheapest and most expensive unused tokens can always be accessed efficiently using two pointers.

The left pointer starts at the beginning of the array and represents the next token to potentially play face-up. The right pointer starts at the end and represents the next token to potentially play face-down.

Inside the loop, the algorithm first prioritizes face-up plays because increasing score is the primary objective. If sufficient power exists, the smallest token is purchased.

Whenever a face-up play succeeds, the current score may become the best score seen so far, so max_score is updated.

If a face-up play is impossible, the algorithm checks whether a face-down play can help. This is only useful when we still have score available and there are remaining tokens worth converting into power.

If neither operation is possible, the loop terminates because no additional score can be gained.

Finally, the maximum score observed during the process is returned.

Go Solution

package main

import "sort"

func bagOfTokensScore(tokens []int, power int) int {
	sort.Ints(tokens)

	left := 0
	right := len(tokens) - 1

	score := 0
	maxScore := 0

	for left <= right {
		if power >= tokens[left] {
			power -= tokens[left]
			score++
			if score > maxScore {
				maxScore = score
			}
			left++
		} else if score > 0 && left < right {
			power += tokens[right]
			score--
			right--
		} else {
			break
		}
	}

	return maxScore
}

The Go implementation follows exactly the same greedy logic as the Python version.

The primary difference is the use of sort.Ints(tokens) for sorting the slice in place. Go slices behave similarly to dynamic arrays, so no additional copying is necessary.

Integer overflow is not a concern because the constraints are small. The implementation also naturally handles empty slices because right becomes -1, causing the loop condition to fail immediately.

Worked Examples

Example 1

Input:

tokens = [100]
power = 50

Sorted tokens:

[100]
Step Left Right Power Score Action
Start 0 0 50 0 Initial state
Cannot play 0 0 50 0 Not enough power, no score to trade

Final answer:

0

Example 2

Input:

tokens = [200, 100]
power = 150

Sorted tokens:

[100, 200]
Step Left Right Power Score Action
Start 0 1 150 0 Initial state
1 1 1 50 1 Play 100 face-up
Stop 1 1 50 1 Cannot afford 200

Maximum score:

1

Example 3

Input:

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

Sorted tokens:

[100, 200, 300, 400]
Step Left Right Power Score Action
Start 0 3 200 0 Initial state
1 1 3 100 1 Play 100 face-up
2 1 2 500 0 Play 400 face-down
3 2 2 300 1 Play 200 face-up
4 3 2 0 2 Play 300 face-up

Maximum score:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) excluding sort Only pointer and counter variables are used

The dominant operation is sorting the token array, which requires O(n log n) time.

After sorting, the two-pointer traversal processes each token at most once from either side, resulting in a linear scan.

The algorithm itself only uses a few integer variables. Ignoring the sorting implementation details, the extra space usage is constant.

Test Cases

from typing import List

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

        left = 0
        right = len(tokens) - 1

        score = 0
        max_score = 0

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

        return max_score

solution = Solution()

assert solution.bagOfTokensScore([100], 50) == 0  # cannot play any token
assert solution.bagOfTokensScore([200, 100], 150) == 1  # one affordable token
assert solution.bagOfTokensScore([100, 200, 300, 400], 200) == 2  # requires trade strategy

assert solution.bagOfTokensScore([], 100) == 0  # empty token list
assert solution.bagOfTokensScore([50], 50) == 1  # exact power match
assert solution.bagOfTokensScore([0], 0) == 1  # zero-cost token
assert solution.bagOfTokensScore([0, 0, 0], 0) == 3  # multiple free tokens

assert solution.bagOfTokensScore([100, 200], 50) == 0  # insufficient power
assert solution.bagOfTokensScore([25, 50, 75], 100) == 2  # partial completion
assert solution.bagOfTokensScore([100, 200, 300], 600) == 3  # can buy all tokens

assert solution.bagOfTokensScore([71, 55, 82], 54) == 0  # close but still impossible
assert solution.bagOfTokensScore([26], 51) == 1  # single affordable token

assert solution.bagOfTokensScore(
    [91, 4, 75, 60, 24, 75, 74, 29, 53, 66],
    35
) == 2  # complex greedy interaction
Test Why
[100], 50 Verifies impossible starting state
[200, 100], 150 Validates simple successful purchase
[100, 200, 300, 400], 200 Confirms optimal trading behavior
[], 100 Ensures empty input works
[50], 50 Tests exact power equality
[0], 0 Verifies zero-cost token handling
[0, 0, 0], 0 Ensures multiple free gains work
[100, 200], 50 Confirms no invalid trades occur
[25, 50, 75], 100 Tests partial token usage
[100, 200, 300], 600 Verifies all tokens can be purchased
[71, 55, 82], 54 Tests near-threshold failure
[26], 51 Small valid input
Larger mixed case Stress tests greedy correctness

Edge Cases

Empty Token Array

If the input array is empty, there are no possible moves. A careless implementation might attempt to initialize pointers incorrectly or access nonexistent elements.

This implementation handles the case naturally because:

right = len(tokens) - 1

becomes -1, so the main loop condition immediately fails.

Insufficient Initial Power

Consider:

tokens = [100]
power = 50

The player cannot afford any face-up move and has no score available for face-down moves.

A buggy implementation might accidentally allow invalid trades or enter an infinite loop. This solution correctly terminates because neither branch of the loop can execute.

Zero-Value Tokens

Tokens may contain value 0.

For example:

tokens = [0, 0, 0]
power = 0

Each token can be played face-up for free, producing score without consuming power.

Some implementations incorrectly assume token values are positive and may mishandle this case. The greedy logic here still works correctly because:

power >= tokens[left]

is true when both values are zero.

Preventing Wasteful Face-Down Trades

The condition:

left < right

is subtle but important.

If only one token remains, spending score to gain power from that token is useless because there would be no remaining token to buy afterward.

Without this condition, an implementation could perform pointless trades that reduce the final score. This solution avoids unnecessary face-down plays and preserves correctness.