{x}
blog image

Bag of Tokens

You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

  • Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
  • Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.

Return the maximum possible score you can achieve after playing any number of tokens.

 

Example 1:

Input: tokens = [100], power = 50

Output: 0

Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).

Example 2:

Input: tokens = [200,100], power = 150

Output: 1

Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.

There is no need to play token0, since you cannot play it face-up to add to your score. The maximum score achievable is 1.

Example 3:

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

Output: 2

Explanation: Play the tokens in this order to get a score of 2:

  1. Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
  2. Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
  3. Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
  4. Play token2 (300) face-up, reducing power to 0 and increasing score to 2.

The maximum score achievable is 2.

 

Constraints:

  • 0 <= tokens.length <= 1000
  • 0 <= tokens[i], power < 104

Solution Explanation: Bag of Tokens

This problem can be efficiently solved using a greedy approach combined with sorting and two pointers. The core idea is to prioritize maximizing the score by strategically using tokens.

Algorithm:

  1. Sort Tokens: Sort the tokens array in ascending order. This allows us to efficiently pick the lowest-cost tokens to increase our score and the highest-value tokens to increase our power when needed.

  2. Two Pointers: Initialize two pointers, left and right, pointing to the beginning and end of the sorted tokens array, respectively. left represents the tokens we'll use to increase our score (lowest cost), and right represents the tokens we'll use to increase our power (highest value) if necessary.

  3. Greedy Strategy:

    • Increase Score: If our current power is greater than or equal to the value of the token at left, we use this token. We subtract the token's value from our power and increment our score. We move left to the next token.
    • Increase Power: If our power is insufficient to use the token at left, but we have a score greater than 0, we use a token from the right end. This allows us to trade a point for increased power. We add the token's value to our power and decrement our score. We move right to the next token.
    • Termination: The loop terminates when either left crosses right (we've used all tokens) or when left cannot be used and we have no score left (we can't increase our power).

  4. Return Maximum Score: The maximum score achieved throughout the process is returned.

Time Complexity Analysis:

  • Sorting the tokens takes O(n log n) time, where n is the number of tokens.
  • The two-pointer iteration takes O(n) time in the worst case (all tokens are used).
  • Therefore, the overall time complexity is dominated by sorting, resulting in O(n log n).

Space Complexity Analysis:

  • Sorting might use O(log n) space in some implementations (e.g., merge sort).
  • The rest of the algorithm uses constant extra space.
  • Thus, the space complexity is O(log n).

Code Examples:

The code examples in Python, Java, C++, Go, and TypeScript provided in the original response all implement this algorithm effectively. The structure is very similar across languages: sort the tokens, use two pointers, and implement the greedy strategy described above. The choice of language will primarily affect the syntax but not the underlying algorithmic efficiency.