# Bag of Tokens
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/bag-of-tokens)
Canonical: https://scaleengineer.com/dsa/problems/bag-of-tokens
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Flexport](https://scaleengineer.com/companies/flexport)
---
## Problem
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_1_ (`100`) face-up, reducing your power to `50` and increasing your score to `1`.

There is no need to play token_0_, 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_0_ (`100`) face-up, reducing power to `100` and increasing score to `1`.
2. Play token_3_ (`400`) face-down, increasing power to `500` and reducing score to `0`.
3. Play token_1_ (`200`) face-up, reducing power to `300` and increasing score to `1`.
4. Play token_2_ (`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`

# Approaches
## Greedy Simulation without Sorting
This approach simulates the process greedily without the initial sorting step. In each step of the simulation, we decide whether to play a token face-up or face-down. To maximize our score, we should play the cheapest possible token face-up. If we cannot afford any token face-up, we might need to gain power by playing a token face-down. To maximize the power gain, we should use the most expensive available token.
**Time:** O(N^2), where N is the number of tokens. The main loop runs up to N times, and inside it, we perform linear scans (O(N)) to find the appropriate token to play. · **Space:** O(N), where N is the number of tokens. This is required for the `used` array to keep track of played tokens.
**Pros:** Follows the greedy logic correctly without altering the original array's order.; Conceptually simple to understand as a direct simulation.
**Cons:** Inefficient due to repeated linear scans to find the minimum and maximum available tokens.; More complex implementation compared to the sorted approach.
### Explanation
We maintain a boolean array `used` to keep track of unplayed tokens. The simulation proceeds in a loop:

1.  First, we try to play a token face-up. We iterate through all unplayed tokens to find the one with the minimum value that we can afford (i.e., `power >= token_value`).
2.  If such a token is found, we play it: decrease `power`, increase `score`, mark the token as used, and update our `maxScore`.
3.  If no token can be played face-up, we check if we can play a token face-down (i.e., `score > 0`). To make this move worthwhile, we only do it if there are other tokens left. We iterate through all unplayed tokens to find the one with the maximum value, play it by increasing `power` and decreasing `score`, and mark it as used.
4.  If we can neither play face-up nor face-down, the game ends, and we break the loop.

The loop continues as long as we can make moves and there are tokens left.

```java
public int bagOfTokensScore(int[] tokens, int power) {
    int n = tokens.length;
    boolean[] used = new boolean[n];
    int score = 0;
    int maxScore = 0;
    int tokensLeft = n;

    while (tokensLeft > 0) {
        // Try to play face-up
        int minTokenIndex = -1;
        int minTokenValue = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (!used[i] && power >= tokens[i] && tokens[i] < minTokenValue) {
                minTokenValue = tokens[i];
                minTokenIndex = i;
            }
        }

        if (minTokenIndex != -1) {
            power -= tokens[minTokenIndex];
            score++;
            used[minTokenIndex] = true;
            tokensLeft--;
            maxScore = Math.max(maxScore, score);
            continue; // Move to next turn
        }

        // Try to play face-down
        if (score > 0 && tokensLeft > 1) {
            int maxTokenIndex = -1;
            int maxTokenValue = -1;
            for (int i = 0; i < n; i++) {
                if (!used[i] && tokens[i] > maxTokenValue) {
                    maxTokenValue = tokens[i];
                    maxTokenIndex = i;
                }
            }
            
            if (maxTokenIndex != -1) {
                power += tokens[maxTokenIndex];
                score--;
                used[maxTokenIndex] = true;
                tokensLeft--;
                continue; // Move to next turn
            }
        }
        
        // If no move could be made, break
        break;
    }

    return maxScore;
}
```
### Algorithm
- Create a boolean array `used` of the same size as `tokens` to track which tokens have been played.
- Initialize `score = 0`, `maxScore = 0`, and `tokensLeft = n`.
- Loop as long as `tokensLeft > 0`:
  - **Attempt Face-Up Play:**
    - Iterate through all tokens to find the unplayed token with the minimum value (`minTokenValue`) that can be afforded (`power >= token value`).
    - If such a token is found at `minIndex`:
      - Update `power -= minTokenValue`, `score++`, `maxScore = max(maxScore, score)`.
      - Mark the token as used: `used[minIndex] = true` and decrement `tokensLeft`.
      - `continue` to the next turn.
  - **Attempt Face-Down Play:**
    - If no face-up move was possible, check if `score > 0` and `tokensLeft > 1`.
    - Iterate through all unplayed tokens to find the one with the maximum value (`maxTokenValue`).
    - If a token is found at `maxIndex`:
      - Update `power += maxTokenValue`, `score--`.
      - Mark the token as used: `used[maxIndex] = true` and decrement `tokensLeft`.
      - `continue` to the next turn.
  - **End Game:**
    - If no move could be made in the current loop iteration, `break`.
- Return `maxScore`.

## Greedy Two-Pointer Approach
This is an efficient and optimal approach that relies on a greedy strategy. The core idea is that to maximize score, we should spend as little power as possible. This means playing the smallest value tokens face-up. Conversely, if we need to gain power by playing a token face-down, we should gain as much power as possible. This means playing the largest value tokens face-down. This naturally leads to sorting the tokens first.
**Time:** O(N log N), where N is the number of tokens. The dominant operation is sorting the array. The two-pointer traversal is O(N). · **Space:** O(log N) or O(N). This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitives has an average space complexity of O(log N) for the recursion stack.
**Pros:** Highly efficient and guaranteed to find the optimal solution.; The logic is clean and directly implements the greedy strategy.; The two-pointer technique avoids repeated searches for min/max tokens.
**Cons:** Requires modifying the input array by sorting it, or using extra space to store a sorted copy.
### Explanation
1.  First, we sort the `tokens` array. This allows us to access the cheapest and most expensive available tokens in O(1) time using pointers.
2.  We use two pointers, `left` starting at index 0 (smallest token) and `right` starting at the last index (largest token).
3.  We iterate as long as `left <= right`. In each step, we make a greedy choice:
    *   **If we can afford `tokens[left]`:** It's always optimal to play it face-up. We gain 1 score for the minimum power cost. We update `power`, `score`, and `maxScore`, and advance `left`.
    *   **If we cannot afford `tokens[left]`:** We check if we have score to trade for power (`score > 0`). If so, we play `tokens[right]` face-down to get the maximum power boost. We update `power` and `score`, and move `right` inwards. We only do this if `left < right`, as playing the last token face-down is never optimal.
    *   **If neither is possible:** We cannot make any more moves to increase our score, so we stop.
4.  Finally, we return `maxScore`.

```java
import java.util.Arrays;

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int left = 0;
        int right = tokens.length - 1;
        int score = 0;
        int maxScore = 0;

        while (left <= right) {
            // Play face-up if possible
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = Math.max(maxScore, score);
            } 
            // Else, play face-down if possible and beneficial
            else if (score > 0 && left < right) {
                power += tokens[right];
                score--;
                right--;
            } 
            // Otherwise, we can't make any more moves to increase score
            else {
                break;
            }
        }
        return maxScore;
    }
}
```
### Algorithm
- Sort the `tokens` array in non-decreasing order.
- Initialize two pointers, `left = 0` and `right = tokens.length - 1`.
- Initialize `score = 0` and `maxScore = 0`.
- Loop while `left <= right`:
  - If `power >= tokens[left]`:
    - Play the token at `left` face-up: `power -= tokens[left]`, `score++`.
    - Move the left pointer: `left++`.
    - Update the maximum score seen: `maxScore = max(maxScore, score)`.
  - Else if `score > 0` and `left < right` (it's only beneficial to trade score for power if there's another token to potentially play):
    - Play the token at `right` face-down: `power += tokens[right]`, `score--`.
    - Move the right pointer: `right--`.
  - Else (cannot make any more productive moves):
    - `break` the loop.
- Return `maxScore`.

# Solutions
### Java

```java
class Solution {
public
  int bagOfTokensScore(int[] tokens, int power) {
    Arrays.sort(tokens);
    int i = 0, j = tokens.length - 1;
    int ans = 0, t = 0;
    while (i <= j) {
      if (power >= tokens[i]) {
        power -= tokens[i++];
        ++t;
        ans = Math.max(ans, t);
      } else if (t > 0) {
        power += tokens[j--];
        --t;
      } else {
        break;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int bagOfTokensScore ( vector < int >& tokens , int power ) { sort ( tokens . begin (), tokens . end ()); int i = 0 , j = tokens . size () - 1 ; int ans = 0 , t = 0 ; while ( i <= j ) { if ( power >= tokens [ i ]) { power -= tokens [ i ++ ]; ans = max ( ans , ++ t ); } else if ( t ) { power += tokens [ j -- ]; -- t ; } else { break ; } } return ans ; } };
```

### Python

```python
class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int: tokens . sort() i, j = 0, len(tokens) - 1 ans = t = 0 while i <= j: if power >= tokens[i]: power -= tokens[i] i, t = i + 1, t + 1 ans = max(ans, t) elif t: power += tokens[j] j, t = j - 1, t - 1 else: break return ans

```