Bag of Tokens

How it works

To maximize our score, we should be strategic about which tokens we play face-up (losing power, gaining score) versus face-down (gaining power, losing score). The key insight is that when gaining score, we want to spend as little power as possible, and when gaining power, we want to gain as much as possible. Sorting the tokens lets us always play the smallest token face-up and the largest token face-down.

Steps

1. Sort the tokens in ascending order.
2. Use two pointers: l starts at the beginning, r at the end.
3. While l <= r:
   • If we have enough power to play tokens[l] face-up, do it (gain 1 score, lose that power). Update the maximum score seen.
   • Else if we have at least 1 score, play tokens[r] face-down (lose 1 score, gain that power).
   • Otherwise, we can't make any more moves, so break.
4. Return the maximum score achieved.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Forgetting to Sort the Tokens

The greedy approach only works on sorted tokens. Without sorting, you cannot guarantee playing the smallest token face-up and largest face-down.

Playing Face-Down with Zero Score

You cannot play a token face-down to gain power unless you have at least 1 score to spend. Attempting this leads to incorrect results.

Returning Current Score Instead of Maximum

The score fluctuates as you play tokens face-down. You must track the maximum score achieved, not just the final score.

from typing import List

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        res = score = 0
        tokens.sort()
        l, r = 0, len(tokens) - 1
        while l <= r:
            if power >= tokens[l]:
                power -= tokens[l]
                l += 1
                score += 1
                res = max(res, score)
            elif score > 0:
                power += tokens[r]
                r -= 1
                score -= 1
            else:
                break
        return res

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int res = 0, score = 0, l = 0, r = tokens.size() - 1;

        while (l <= r) {
            if (power >= tokens[l]) {
                power -= tokens[l++];
                score++;
                res = max(res, score);
            } else if (score > 0) {
                power += tokens[r--];
                score--;
            } else {
                break;
            }
        }

        return res;
    }
};