Bag of Tokens: Greedy Two-Pointer Strategy

You have an initial power and an array of tokens where each token has a value. You can play each token at most once, in any order, in one of two ways: face up (spend tokens[i] power and gain 1 score) or face down (spend 1 score and gain tokens[i] power). Return the maximum score you can achieve after playing any number of tokens.

This is LeetCode 948: Bag of Tokens, a medium problem that combines sorting with a greedy two-pointer strategy. The core tension is that cheap tokens are worth spending power on, while expensive tokens are worth sacrificing score for. Sorting makes that distinction crisp.

Why this problem matters

Bag of Tokens teaches you to think about two-way resource trading. You have two currencies (power and score), and each token lets you convert one into the other. The question is which direction to convert and in what order.

This pattern of "spend the cheap resource, recoup with the expensive resource" shows up across greedy and two-pointer problems. Once you see that sorting separates the cheap tokens from the expensive ones, the two-pointer approach falls into place naturally. The left pointer handles face-up plays (cheap tokens, spend power) and the right pointer handles face-down plays (expensive tokens, spend score).

Understanding this problem builds intuition for any scenario where you need to balance two competing resources optimally.

The brute force approach

A brute force solution would try every possible subset of tokens and every possible face-up or face-down assignment for each. With n tokens, each token has three choices (skip, face up, face down), giving 3^n combinations.

def bagOfTokensScore_brute(tokens, power):
    n = len(tokens)
    max_score = 0
    for mask in range(3 ** n):
        p, s = power, 0
        temp = mask
        valid = True
        for i in range(n):
            choice = temp % 3
            temp //= 3
            if choice == 1:
                p -= tokens[i]
                if p < 0:
                    valid = False
                    break
                s += 1
            elif choice == 2:
                s -= 1
                if s < 0:
                    valid = False
                    break
                p += tokens[i]
        if valid:
            max_score = max(max_score, s)
    return max_score

This works for tiny inputs but is completely impractical for real constraints. With n up to 1000, we need something far better.

The key insight: sort and use two pointers

After sorting, the cheapest tokens are on the left and the most expensive tokens are on the right. This creates a natural two-pointer strategy:

• Left pointer (face up): When you have enough power, play the cheapest available token face up. This costs the least power for 1 score, maximizing your score-per-power spent.
• Right pointer (face down): When you are out of power but have score to spend, play the most expensive available token face down. This gives you the most power for 1 score, maximizing your power-per-score spent.

The greedy logic is that you always want to buy score as cheaply as possible and sell score as expensively as possible. Sorting plus two pointers achieves exactly that.

Walking through it step by step

Let's trace through tokens = [100, 200, 300, 400], power = 200. After sorting, the array is already [100, 200, 300, 400]. We track power, score, and maxScore.

The final maximum score is 2. Notice how playing the expensive token (400) face down at step 2 gave us enough power to play two more tokens face up. Without that trade, we would have been stuck at score 1 after the first face-up play.

The greedy solution

def bagOfTokensScore(tokens, power):
    tokens.sort()
    left, right = 0, 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:
            power += tokens[right]
            score -= 1
            right -= 1
        else:
            break

    return max_score

Here is what each piece does:

1. Sort the tokens. This puts cheap tokens on the left and expensive tokens on the right.
2. Two pointers. left starts at index 0 (cheapest), right starts at the last index (most expensive).
3. Face up (left pointer). If you have enough power, play tokens[left] face up. Deduct power, add 1 to score, update max_score, and move left forward.
4. Face down (right pointer). If you cannot afford the left token but have score to spend, play tokens[right] face down. Add that token's value to power, deduct 1 from score, and move right backward.
5. Break. If you cannot play face up (not enough power) and cannot play face down (no score), stop.
6. Track max_score separately because playing face down reduces your score. The maximum score might occur before a face-down play, not at the end.

Complexity analysis

The two-pointer loop visits each token at most once. Each iteration either moves left right, moves right left, or breaks. So the loop body runs at most n times.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy two-pointer on a sorted array

The pattern of sorting an array, then using two pointers from opposite ends to make optimal pairings or trades:

arr.sort()
left, right = 0, len(arr) - 1
while left <= right:
    if can_use_left(arr[left]):
        use_left(arr[left])
        left += 1
    elif can_use_right(arr[right]):
        use_right(arr[right])
        right -= 1
    else:
        break

In Bag of Tokens, the left pointer spends power on cheap tokens and the right pointer spends score on expensive tokens. In Boats to Save People, the left pointer pairs the lightest person with the heaviest. In Two Sum (sorted), the pointers converge toward the target. The skeleton is the same: sort, then shrink the window from both ends with a greedy rule.

2. Resource exchange tracking

The pattern of maintaining multiple resource counters that can be traded against each other:

resource_a = initial_a
resource_b = 0
max_b = 0
for item in sequence:
    if condition_on_a:
        resource_a -= cost
        resource_b += 1
        max_b = max(max_b, resource_b)
    elif resource_b > 0:
        resource_b -= 1
        resource_a += gain

In Bag of Tokens, the resources are power and score. In problems like gas station, the resources are fuel and distance. The idea is the same: track multiple quantities that flow back and forth, and record the peak of the quantity you want to maximize.

Edge cases

Before submitting, make sure your solution handles these:

• Empty array tokens = []: no tokens to play. Return 0.
• Single token, enough power tokens = [50], power = 100: play it face up. Score = 1.
• Single token, not enough power tokens = [200], power = 50: cannot play face up, no score to play face down. Return 0.
• All tokens affordable tokens = [10, 20, 30], power = 100: play all face up. Score = 3.
• No tokens affordable tokens = [500, 600], power = 10: cannot play any token face up, no score to start with. Return 0.
• Power equals cheapest token tokens = [100, 200], power = 100: play token[0] face up (score = 1, power = 0). Cannot afford token[1], but could play it face down (score = 0, power = 200). Max score = 1, achieved before the face-down play.

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Not tracking max_score separately from score. After a face-down play, your score decreases. If you return score at the end instead of max_score, you might report a lower value than the actual maximum achieved during the process.

2. Forgetting to sort. The entire greedy strategy depends on cheap tokens being on the left and expensive tokens being on the right. Without sorting, the two-pointer approach produces wrong results.

3. Playing face down when score is 0. You need at least 1 score to play a token face down. If you skip this check, you go negative and produce an invalid result.

4. Not breaking when stuck. If you cannot play face up (not enough power) and cannot play face down (no score), you must stop the loop. Without the break, you enter an infinite loop.

5. Using the wrong pointer direction for face down. Face-down plays should consume the most expensive remaining token (right pointer), not the cheapest. Using the left pointer for face down wastes potential power gain.

From understanding to recall

You have read the greedy two-pointer solution and it makes sense. Sort, play cheap tokens face up from the left, play expensive tokens face down from the right, track the maximum score. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: sorting first, checking power >= tokens[left] before score > 0, updating max_score only on face-up plays, and breaking when neither action is possible. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy two-pointer loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize score with two-way token trades" and the code flows out without hesitation.

The greedy two-pointer pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Lemonade Change - A greedy problem where a simple priority rule replaces brute-force search over change combinations
• Boats to Save People - Greedy two-pointer pairing on a sorted array to minimize boats
• Advantage Shuffle - Greedy matching of sorted arrays to maximize pairwise advantage

CodeBricks breaks the bag of tokens LeetCode problem into its greedy two-pointer and resource exchange building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy resource-trading question shows up in your interview, you do not think about it. You just write it.