Problem Description

You have a bag of tokens, each with a specific value, and you start with some initial power and a score of 0. Your goal is to maximize your score by strategically playing these tokens.

Each token can be played in one of two ways (but only once per token):

1. Face-up: If you have enough power (at least tokens[i]), you can spend tokens[i] power to gain 1 score point.

2. Face-down: If you have at least 1 score point, you can spend 1 score point to gain tokens[i] power.

The strategy involves finding the optimal way to play tokens to achieve the maximum possible score. You can play any number of tokens (including none) and in any order.

For example, if you have tokens [100, 200, 300, 400] and initial power of 200:

• You could play token 100 face-up (spend 100 power, gain 1 score), leaving you with 100 power and 1 score
• Then play token 400 face-down (spend 1 score, gain 400 power), leaving you with 500 power and 0 score
• Then play tokens 200 and 300 face-up to end with 2 score

The solution uses a greedy approach with two pointers after sorting. It tries to gain score by playing smaller tokens face-up (using minimal power) and when power runs low, it plays larger tokens face-down (trading score for maximum power gain). This ensures we get the most score possible from our available resources.

Intuition

The key insight is recognizing that we want to maximize score while being strategic about power management. Since playing face-up costs power but gains score, and playing face-down costs score but gains power, we need to find the optimal trade-off.

Think of it like buying and selling: we want to "buy" score points as cheaply as possible (using minimal power) and when we need more power, we want to "sell" score points for maximum power gain.

This naturally leads to a greedy strategy:

• When gaining score (face-up), use the tokens that cost the least power
• When gaining power (face-down), use the tokens that give the most power

By sorting the tokens, we create this optimal arrangement: smallest values on the left (cheap to play face-up) and largest values on the right (valuable to play face-down).

The two-pointer approach emerges from this insight. We maintain pointers at both ends:

• Left pointer (i) tracks the cheapest unplayed token for gaining score
• Right pointer (j) tracks the most valuable unplayed token for gaining power

At each step, we make a greedy decision:

1. If we have enough power for tokens[i], play it face-up to gain score (this is always beneficial since we're using the cheapest available token)
2. If we don't have enough power but have score to spare, play tokens[j] face-down to gain maximum power (this gives us the best "exchange rate" for our score point)
3. If we can't do either, we're stuck and should stop

We track the maximum score achieved at any point because sometimes it's optimal to end with leftover power rather than trading more score for power that won't be fully utilized.

Learn more about Greedy, Two Pointers and Sorting patterns.

Solution Approach

The implementation follows a greedy strategy with sorting and two pointers:

1. Sort the tokens array: First, we sort tokens in ascending order. This arrangement allows us to access the cheapest tokens from the left and the most valuable tokens from the right.

2. Initialize variables:

   • ans tracks the maximum score achieved at any point
   • score tracks the current score
   • i and j are two pointers starting at the beginning and end of the sorted array respectively

3. Main loop with two-pointer technique: While i <= j (meaning we still have unplayed tokens):

   a. Try to play face-up (gain score): If power >= tokens[i], we have enough power to play the cheapest available token:

   • Decrease power by tokens[i]
   • Increase score by 1
   • Move left pointer i forward
   • Update ans = max(ans, score) to track the maximum score

   b. Try to play face-down (gain power): If we don't have enough power for the cheapest token but have at least 1 score point:

   • Increase power by tokens[j] (the most valuable token)
   • Decrease score by 1
   • Move right pointer j backward

   c. Cannot play: If we have neither enough power for the cheapest token nor any score to trade, break out of the loop

4. Return the maximum score: Return ans, which holds the highest score achieved during the process.

The algorithm ensures optimal play by always:

• Spending the least amount of power when gaining score (using smallest tokens)
• Gaining the maximum amount of power when trading score (using largest tokens)
• Tracking the peak score since the final score might not be the maximum (we might trade score for power that doesn't get fully utilized)

Time complexity: O(n log n) for sorting, where n is the number of tokens. Space complexity: O(1) if we don't count the sorting space.

Example Walkthrough

Let's walk through a small example with tokens = [100, 200, 300, 400] and power = 250.

Step 1: Sort the tokens Tokens are already sorted: [100, 200, 300, 400]

Step 2: Initialize variables

• ans = 0 (maximum score tracker)
• score = 0 (current score)
• i = 0 (left pointer at token 100)
• j = 3 (right pointer at token 400)
• power = 250

Step 3: Main loop iterations

Iteration 1: i = 0, j = 3

• Check: Can play face-up? power (250) >= tokens[0] (100)? Yes!
• Play token 100 face-up: power = 250 - 100 = 150, score = 0 + 1 = 1
• Move i to 1
• Update ans = max(0, 1) = 1

Iteration 2: i = 1, j = 3

• Check: Can play face-up? power (150) >= tokens[1] (200)? No
• Check: Can play face-down? score (1) > 0? Yes!
• Play token 400 face-down: power = 150 + 400 = 550, score = 1 - 1 = 0
• Move j to 2

Iteration 3: i = 1, j = 2

• Check: Can play face-up? power (550) >= tokens[1] (200)? Yes!
• Play token 200 face-up: power = 550 - 200 = 350, score = 0 + 1 = 1
• Move i to 2
• Update ans = max(1, 1) = 1

Iteration 4: i = 2, j = 2

• Check: Can play face-up? power (350) >= tokens[2] (300)? Yes!
• Play token 300 face-up: power = 350 - 300 = 50, score = 1 + 1 = 2
• Move i to 3
• Update ans = max(1, 2) = 2

Loop ends: i (3) > j (2)

Result: Maximum score = 2

The strategy worked by first playing the cheapest token (100) to gain initial score, then trading that score for maximum power (400), and finally using that power to play the remaining tokens (200 and 300) to maximize the final score.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The time complexity is dominated by the sorting operation tokens.sort() which takes O(n log n) time where n is the number of tokens. After sorting, the while loop runs with two pointers i and j moving towards each other. In the worst case, each token is visited at most once, taking O(n) time. Therefore, the overall time complexity is O(n log n) + O(n) = O(n log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's sort() method uses Timsort, which has a worst-case space complexity of O(n) but typically uses O(log n) space for the recursion stack in practice. The algorithm itself only uses a constant amount of extra space for variables (ans, score, i, j), which is O(1). Therefore, the overall space complexity is O(log n) due to the sorting operation.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Returning Current Score Instead of Maximum Score

A frequent mistake is returning current_score at the end instead of tracking and returning the maximum score achieved during the process. The current score at the end might be lower than the peak score reached during gameplay.

Incorrect Implementation:

def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
    tokens.sort()
    current_score = 0
    left, right = 0, len(tokens) - 1
  
    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            current_score += 1
            left += 1
        elif current_score > 0:
            power += tokens[right]
            current_score -= 1
            right -= 1
        else:
            break
  
    return current_score  # Wrong! Returns final score, not maximum

Why This Fails: Consider tokens = [100, 200] with power = 150:

• Play token 100 face-up: score = 1, power = 50
• Can't play token 200 face-up (insufficient power)
• Play token 200 face-down: score = 0, power = 250
• Final score is 0, but maximum achieved was 1

Correct Approach: Always track the maximum score with max_score = max(max_score, current_score) after gaining points, and return max_score instead of current_score.

2. Updating Maximum Score at the Wrong Time

Another pitfall is updating the maximum score after both face-up and face-down plays, or only at the end of the loop.

Incorrect Implementation:

while left <= right:
    if power >= tokens[left]:
        power -= tokens[left]
        current_score += 1
        left += 1
    elif current_score > 0:
        power += tokens[right]
        current_score -= 1
        right -= 1
        max_score = max(max_score, current_score)  # Wrong timing!
    else:
        break

Why This Fails: The maximum score should only be updated when we gain score (face-up play), not when we lose score (face-down play). Updating after face-down plays would miss capturing the peak score before it decreases.

Correct Approach: Only update max_score immediately after increasing current_score in the face-up branch:

if power >= tokens[left]:
    power -= tokens[left]
    current_score += 1
    left += 1
    max_score = max(max_score, current_score)  # Update only here