# LeetCode 948: Bag of Tokens

## Problem Restatement

We are given an array of token values:

```python
tokens
```

and an initial amount of power:

```python
power
```

We start with score `0`.

Each token may be played at most once, in one of two ways:

| Play type | Requirement | Effect |
|---|---|---|
| Face-up | `power >= token` | Lose `token` power, gain `1` score |
| Face-down | `score >= 1` | Gain `token` power, lose `1` score |

We may play any number of tokens in any order.

Return the maximum score we can achieve. The official statement defines the same face-up and face-down operations and asks for the maximum possible score.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `tokens`, an integer array |
| Input | Initial integer `power` |
| Output | Maximum score possible |
| Token rule | Each token can be used at most once |
| Starting score | `0` |

Function shape:

```python
class Solution:
    def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
        ...
```

## Examples

Example 1:

```python
tokens = [100]
power = 50
```

We cannot play the token face-up because `50 < 100`.

We also cannot play it face-down because score is `0`.

Answer:

```python
0
```

Example 2:

```python
tokens = [200, 100]
power = 150
```

Play token `100` face-up:

```text
power = 50
score = 1
```

The maximum score is:

```python
1
```

Example 3:

```python
tokens = [100, 200, 300, 400]
power = 200
```

One optimal sequence is:

```text
play 100 face-up   -> power = 100, score = 1
play 400 face-down -> power = 500, score = 0
play 200 face-up   -> power = 300, score = 1
play 300 face-up   -> power = 0,   score = 2
```

Answer:

```python
2
```

These are the standard examples for the problem.

## First Thought

We can try every possible order of playing tokens.

For each token, we may play it face-up, face-down, or skip it.

That creates many possibilities and is not practical.

The choice should be guided by value:

- To gain score, spend as little power as possible.
- To regain power, receive as much power as possible.

This suggests sorting the tokens.

## Key Insight

Sort the tokens.

Use two pointers:

| Pointer | Meaning |
|---|---|
| `left` | Smallest unused token |
| `right` | Largest unused token |

When we can gain score, we should play the smallest token face-up.

This gives `1` score for the lowest power cost.

When we cannot gain score but have at least `1` score, we should play the largest token face-down.

This gives the most power back for one score point.

We also track the highest score ever reached, because playing a token face-down may reduce the current score later.

## Algorithm

Sort `tokens`.

Initialize:

```python
left = 0
right = len(tokens) - 1
score = 0
best = 0
```

While `left <= right`:

1. If we have enough power for the smallest token:
   - play it face-up
   - increase `score`
   - update `best`
   - move `left`

2. Otherwise, if we have at least one score:
   - play the largest token face-down
   - decrease `score`
   - increase `power`
   - move `right`

3. Otherwise:
   - stop

Return `best`.

## Walkthrough

Use:

```python
tokens = [100, 200, 300, 400]
power = 200
```

After sorting:

```python
[100, 200, 300, 400]
```

| Action | Power | Score | Best |
|---|---:|---:|---:|
| Start | 200 | 0 | 0 |
| Play `100` face-up | 100 | 1 | 1 |
| Play `400` face-down | 500 | 0 | 1 |
| Play `200` face-up | 300 | 1 | 1 |
| Play `300` face-up | 0 | 2 | 2 |

The maximum score reached is:

```python
2
```

## Correctness

When playing a token face-up, every unused token gives exactly `1` score. To preserve as much power as possible for future plays, the best choice is the smallest unused token. Any larger face-up token would give the same score while spending more power.

When playing a token face-down, every unused token costs exactly `1` score. To regain as much power as possible, the best choice is the largest unused token. Any smaller face-down token would give less power for the same score cost.

The algorithm applies these two optimal local choices whenever each action is needed.

If the smallest token cannot be played face-up and the current score is `0`, no token can be played face-up, and no token can be played face-down. So no further move is possible.

If the smallest token cannot be played face-up but score is positive, playing the largest token face-down gives the maximum possible power increase and is the best chance to unlock future face-up plays.

The algorithm records the maximum score reached at every point. Since face-down moves may temporarily lower score to enable later gains, the final current score may be lower than the best score achieved.

Therefore, the returned `best` is the maximum score obtainable.

## Complexity

Let:

```python
n = len(tokens)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(1)` or `O(n)` | Depends on sorting implementation |

The two-pointer scan is `O(n)` because each token is used at most once.

## Implementation

```python
class Solution:
    def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
        tokens.sort()

        left = 0
        right = len(tokens) - 1

        score = 0
        best = 0

        while left <= right:
            if power >= tokens[left]:
                power -= tokens[left]
                score += 1
                best = max(best, score)
                left += 1
            elif score > 0:
                power += tokens[right]
                score -= 1
                right -= 1
            else:
                break

        return best
```

## Code Explanation

Sort the tokens first:

```python
tokens.sort()
```

The smallest unused token is at `left`.

The largest unused token is at `right`.

If we can afford the smallest token:

```python
if power >= tokens[left]:
```

we play it face-up:

```python
power -= tokens[left]
score += 1
best = max(best, score)
left += 1
```

If we cannot gain score but have score to spend:

```python
elif score > 0:
```

we play the largest token face-down:

```python
power += tokens[right]
score -= 1
right -= 1
```

If neither action is possible, the process stops:

```python
else:
    break
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.bagOfTokensScore([100], 50) == 0
    assert s.bagOfTokensScore([200, 100], 150) == 1
    assert s.bagOfTokensScore([100, 200, 300, 400], 200) == 2

    assert s.bagOfTokensScore([], 100) == 0
    assert s.bagOfTokensScore([100, 200], 300) == 2
    assert s.bagOfTokensScore([100, 200, 300], 150) == 1
    assert s.bagOfTokensScore([25, 100, 500], 25) == 1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[100]`, power `50` | Cannot play anything |
| `[200,100]`, power `150` | One face-up play |
| `[100,200,300,400]`, power `200` | Needs face-down trade |
| Empty tokens | No score possible |
| Enough power for all | Play all face-up |
| Limited power | Best score stays `1` |
| Small then large token | Checks greedy face-up first |