Code Implementation

class Solution:
    def bagOfTokensScore(self, 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
                left += 1
                max_score = max(max_score, score)
            elif score > 0:
                power += tokens[right]
                score -= 1
                right -= 1
            else:
                break
        return max_score
      

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int left = 0, right = tokens.size() - 1;
        int score = 0, maxScore = 0;
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left++];
                score++;
                maxScore = max(maxScore, score);
            } else if (score > 0) {
                power += tokens[right--];
                score--;
            } else {
                break;
            }
        }
        return maxScore;
    }
};
      

import java.util.Arrays;
class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int left = 0, right = tokens.length - 1;
        int score = 0, maxScore = 0;
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left++];
                score++;
                maxScore = Math.max(maxScore, score);
            } else if (score > 0) {
                power += tokens[right--];
                score--;
            } else {
                break;
            }
        }
        return maxScore;
    }
}
      

var bagOfTokensScore = function(tokens, power) {
    tokens.sort((a, b) => a - b);
    let left = 0, right = tokens.length - 1;
    let score = 0, maxScore = 0;
    while (left <= right) {
        if (power >= tokens[left]) {
            power -= tokens[left++];
            score++;
            maxScore = Math.max(maxScore, score);
        } else if (score > 0) {
            power += tokens[right--];
            score--;
        } else {
            break;
        }
    }
    return maxScore;
};
      

Problem Description

You are given an array of integers called tokens and an integer power. Each token can be played in one of two ways:

• If you have at least as much power as the value of a token, you may spend that much power to gain 1 score (you "play the token face up").
• If you have at least 1 score, you may spend 1 score to gain power equal to the value of a token (you "play the token face down").

• Each token can be used only once.
• You can only play a token face up if you have enough power.
• You can only play a token face down if you have at least 1 score.

Thought Process

At first glance, it seems we might try every possible order of playing tokens, but that would be very slow (brute-force). Instead, let's think about what maximizes our score:

• To gain score, we want to spend the least possible power for each point. So, we should use the lowest-value tokens first when playing face up.
• If we are stuck (can't play any more face up), but have at least 1 score, we can "trade" score for power by playing the largest token face down. This gives us the most power possible for 1 score.
• This suggests a two-pointer approach: use the smallest token to gain score, and if stuck, use the largest token to regain power at the cost of a score.

Solution Approach

We use a greedy, two-pointer strategy:

1. Sort the tokens in increasing order. This allows us to always spend the least power for score, or gain the most power for a score.
2. Initialize two pointers: left at the start (smallest token), right at the end (largest token).
3. While possible, play tokens face up: If your power is at least tokens[left], spend tokens[left] power to gain 1 score, and move left forward.
4. If stuck (can't play face up), but have score > 0: Spend 1 score to gain tokens[right] power, and move right backward.
5. Track the maximum score achieved at any point, since trading score for power might reduce your current score.
6. Stop when neither move is possible (not enough power to play up, and not enough score to play down).

Example Walkthrough

Example Input:
tokens = [100, 200, 300, 400], power = 200

Step-by-step:

1. Sort tokens: [100, 200, 300, 400]
2. Start with power = 200, score = 0, max_score = 0
3. First move: power (200) >= tokens[0] (100) ⇒ play face up, power = 100, score = 1, left = 1
4. Second move: power (100) < tokens[1] (200) ⇒ can't play face up. But score > 0, so play tokens[3] face down: power = 100 + 400 = 500, score = 0, right = 2
5. Third move: power (500) >= tokens[1] (200) ⇒ play face up, power = 300, score = 1, left = 2
6. Fourth move: power (300) >= tokens[2] (300) ⇒ play face up, power = 0, score = 2, left = 3
7. Now, left > right, so we stop.
8. Result: The maximum score achieved was 2.

Time and Space Complexity

Brute-force: Trying every permutation of token orders would be O(n!), which is infeasible for large n.

Optimized (Greedy Two-Pointer):

• Time Complexity: O(n log n) for sorting the tokens, plus O(n) for the two-pointer traversal, so overall O(n log n).
• Space Complexity: O(1) extra space (ignoring the input array and sorting in place), or O(n) if you create a sorted copy.

Summary

The "Bag of Tokens" problem is best solved using a greedy, two-pointer approach. By always using the smallest tokens to gain score and the largest tokens to regain power (if needed), we maximize our score efficiently. The key insight is to alternate between these two actions, tracking the highest score reached at any point. This strategy is both simple and optimal, making the solution elegant and efficient.