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 token*_i*.

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 token*_i*, losing tokens[i] power and gaining 1 score.
• Face-down: If your current score is at least 1, you may play token*_i*, 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 token*₁* (100) face-up, reducing your power to 50 and increasing your score to 1.

There is no need to play token*₀*, 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 token*₀* (100) face-up, reducing power to 100 and increasing score to 1.
2. Play token*₃* (400) face-down, increasing power to 500 and reducing score to 0.
3. Play token*₁* (200) face-up, reducing power to 300 and increasing score to 1.
4. Play token*₂* (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 < 10<sup>4</sup>

class Solution:
    def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
        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

Naive Approach

The most basic approach would be to try every combination of playing tokens face-up and face-down to find the maximum score. This involves recursion and exploring all possible paths.

def bagOfTokensScore_naive(tokens: list[int], power: int) -> int:
    def solve(index: int, current_power: int, current_score: int, played: set[int]) -> int:
        if index == len(tokens):
            return current_score

        max_score = current_score

        # Option 1: Play face-up
        if index not in played and current_power >= tokens[index]:
            played.add(index)
            max_score = max(max_score, solve(index + 1, current_power - tokens[index], current_score + 1, played))
            played.remove(index)

        # Option 2: Play face-down
        if index not in played and current_score >= 1:
            played.add(index)
            max_score = max(max_score, solve(index + 1, current_power + tokens[index], current_score - 1, played))
            played.remove(index)

        # Option 3: Skip this token
        max_score = max(max_score, solve(index + 1, current_power, current_score, played))

        return max_score

    return solve(0, power, 0, set())

The problem with this naive approach is that it has exponential time complexity. The number of possible combinations grows very quickly as the number of tokens increases, making it impractical for larger inputs. The improved solution, using sorting and a two-pointer approach, significantly reduces time complexity.

Optimal Approach: Greedy Algorithm

To maximize the score, we can use a greedy approach. Sort the tokens in ascending order. Play the smallest token face-up as long as we have enough power. If we don't have enough power to play any more tokens face-up, and if we have a score greater than 0, play the largest token face-down to increase our power.

class Solution:
    def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
        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

Example

Consider tokens = [100, 200, 300, 400] and power = 200.

1. Sort tokens: [100, 200, 300, 400].
2. Play 100 face-up: power = 100, score = 1.
3. Play 400 face-down: power = 500, score = 0.
4. Play 200 face-up: power = 300, score = 1.
5. Play 300 face-up: power = 0, score = 2.

The maximum score is 2.

Big O Runtime Analysis

• Sorting: O(n log n), where n is the number of tokens.
• Two-pointer iteration: O(n), where n is the number of tokens. In the worst case, the while loop iterates through all tokens once.

Overall, the time complexity is dominated by the sorting step, so it's O(n log n).

Big O Space Usage Analysis

• Sorting: O(1) or O(n), depending on the sorting algorithm. Python's sort() method has an average time complexity of O(n log n) and a space complexity of O(1).
• Two-pointer variables: O(1) (left, right, score, max_score).

Overall, the space complexity is O(1) if the sorting is in-place, otherwise O(n).

Edge Cases

1. Empty tokens array:
   • If tokens is empty, return 0.
2. Initial power is zero:
   • If power is 0 and there are tokens, the score will always be 0 because you can't play any token face-up.
3. Tokens are very large compared to power:
   • If the smallest token is larger than the initial power, return 0.
4. All tokens are the same:
   • The algorithm should still work correctly. If you can play all tokens face-up, you will. Otherwise, you'll play face-down until you can't anymore.
5. Large number of tokens:
   • The algorithm should scale reasonably well because the time complexity is O(n log n).