# LeetCode 486: Predict the Winner

## Problem Restatement

We are given an integer array `nums`.

Two players play a game with this array.

Player 1 moves first. On each turn, the current player must take one number from either end of the array. That means the player may take either the leftmost number or the rightmost number.

The chosen number is added to that player's score, and the number is removed from the array.

Both players play optimally.

Return `true` if Player 1 can win. A tie also counts as a win for Player 1. The official statement specifies that equal scores should also return `true`, and the constraints are `1 <= nums.length <= 20` and `0 <= nums[i] <= 10^7`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | `true` if Player 1 can win or tie |
| Move rule | Take from the left end or right end |
| Assumption | Both players play optimally |
| Tie rule | Tie counts as Player 1 winning |

Function shape:

```python
def predictTheWinner(nums: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```python
nums = [1, 5, 2]
```

Player 1 can choose either `1` or `2`.

If Player 1 takes `1`, Player 2 takes `5`, then Player 1 gets `2`.

Final scores:

```text
Player 1 = 1 + 2 = 3
Player 2 = 5
```

If Player 1 takes `2`, Player 2 still takes `5`, then Player 1 gets `1`.

Final scores:

```text
Player 1 = 2 + 1 = 3
Player 2 = 5
```

Player 1 cannot win or tie.

Answer:

```python
False
```

Example 2:

```python
nums = [1, 5, 233, 7]
```

Player 1 can take `1`.

Then Player 2 must choose between `5` and `7`.

No matter which one Player 2 chooses, Player 1 can take `233`.

Final result can be:

```text
Player 1 = 1 + 233 = 234
Player 2 = 7 + 5 = 12
```

Player 1 wins.

Answer:

```python
True
```

## First Thought: Simulate Every Game

A direct solution is to try every possible sequence of moves.

At each turn, the current player has two choices:

1. Take the left number.
2. Take the right number.

This forms a recursion tree.

For example:

```python
nums = [1, 5, 2]
```

Player 1 can take `1` or `2`.

Then Player 2 also chooses from the remaining ends.

This approach can find the answer, but it repeats the same subproblems many times.

## Problem With Plain Recursion

The array length can be up to `20`.

Each move branches into two choices, so plain recursion can take roughly:

```text
O(2^n)
```

That is avoidable because the game state is fully described by the remaining interval:

```text
left index, right index
```

The same interval may be reached through different previous choices.

So we use dynamic programming.

## Key Insight

Instead of tracking both players' scores separately, track the score difference from the current player's point of view.

Define:

```text
dp(left, right)
```

as the maximum score difference the current player can achieve over the other player using only:

```python
nums[left:right + 1]
```

A positive value means the current player can finish ahead from this subarray.

A zero value means the current player can tie.

A negative value means the current player falls behind.

On the current turn, there are two choices.

If the player takes `nums[left]`, the opponent becomes the current player for the remaining subarray `left + 1` to `right`.

The opponent can then achieve:

```text
dp(left + 1, right)
```

against us.

So our net score difference from taking left is:

```text
nums[left] - dp(left + 1, right)
```

Similarly, taking right gives:

```text
nums[right] - dp(left, right - 1)
```

We choose the better option:

```text
dp(left, right) = max(
    nums[left] - dp(left + 1, right),
    nums[right] - dp(left, right - 1)
)
```

## Algorithm

Use recursion with memoization.

For `dp(left, right)`:

1. If `left == right`, only one number remains, so return `nums[left]`.
2. Compute the result if taking the left number.
3. Compute the result if taking the right number.
4. Return the larger score difference.

At the end, Player 1 can win or tie if:

```python
dp(0, len(nums) - 1) >= 0
```

## Correctness

The function `dp(left, right)` represents the best score difference the current player can force from the subarray `nums[left:right + 1]`.

If only one number remains, the current player takes it, and the score difference is exactly that number.

For a longer interval, the current player has exactly two legal moves: take the left end or take the right end.

If the current player takes the left value, they gain `nums[left]`. The opponent then becomes the current player on the remaining interval. Since `dp(left + 1, right)` is the best score difference the opponent can force from there, the original player's final advantage is `nums[left] - dp(left + 1, right)`.

The same reasoning gives `nums[right] - dp(left, right - 1)` for taking the right value.

The current player plays optimally, so the correct value is the maximum of those two choices.

By induction on interval length, `dp(left, right)` is correct for every interval. Therefore, `dp(0, n - 1)` is the best final score difference Player 1 can force for the whole game. Player 1 wins or ties exactly when this value is at least zero.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | There are `O(n^2)` intervals |
| Space | `O(n^2)` | Memoization stores one value per interval |

The recursion depth is `O(n)`.

## Implementation

```python
from functools import cache

class Solution:
    def predictTheWinner(self, nums: list[int]) -> bool:
        @cache
        def dp(left: int, right: int) -> int:
            if left == right:
                return nums[left]

            take_left = nums[left] - dp(left + 1, right)
            take_right = nums[right] - dp(left, right - 1)

            return max(take_left, take_right)

        return dp(0, len(nums) - 1) >= 0
```

## Code Explanation

The memoized function stores the best score difference for each interval:

```python
@cache
def dp(left: int, right: int) -> int:
```

The base case is one remaining number:

```python
if left == right:
    return nums[left]
```

If we take the left number, the opponent controls the remaining interval:

```python
take_left = nums[left] - dp(left + 1, right)
```

If we take the right number, the same logic applies:

```python
take_right = nums[right] - dp(left, right - 1)
```

We choose the better move:

```python
return max(take_left, take_right)
```

Finally, Player 1 can win or tie if the final difference is non-negative:

```python
return dp(0, len(nums) - 1) >= 0
```

## Bottom-Up Implementation

The same recurrence can be written iteratively.

Let `dp[i][j]` mean the best score difference the current player can force from `nums[i:j + 1]`.

```python
class Solution:
    def predictTheWinner(self, nums: list[int]) -> bool:
        n = len(nums)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = nums[i]

        for length in range(2, n + 1):
            for left in range(n - length + 1):
                right = left + length - 1

                take_left = nums[left] - dp[left + 1][right]
                take_right = nums[right] - dp[left][right - 1]

                dp[left][right] = max(take_left, take_right)

        return dp[0][n - 1] >= 0
```

## Testing

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

    assert s.predictTheWinner([1, 5, 2]) is False
    assert s.predictTheWinner([1, 5, 233, 7]) is True
    assert s.predictTheWinner([1]) is True
    assert s.predictTheWinner([1, 1]) is True
    assert s.predictTheWinner([2, 4, 55, 6, 8]) is False
    assert s.predictTheWinner([0, 0, 0]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 5, 2]` | Player 1 cannot avoid losing |
| `[1, 5, 233, 7]` | Player 1 can force a win |
| `[1]` | Single number always wins |
| `[1, 1]` | Tie counts as Player 1 winning |
| `[2, 4, 55, 6, 8]` | Checks non-greedy optimal play |
| `[0, 0, 0]` | Tie with zero scores |