# Predict the Winner
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/predict-the-winner)
Canonical: https://scaleengineer.com/dsa/problems/predict-the-winner
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** Array
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Flipkart](https://scaleengineer.com/companies/flipkart), [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## Problem
You are given an integer array `nums`. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of `0`. At each turn, the player takes one of the numbers from either end of the array (i.e., `nums[0]` or `nums[nums.length - 1]`) which reduces the size of the array by `1`. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return `true` if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return `true`. You may assume that both players are playing optimally.

**Example 1:**

**Input:** nums = [1,5,2]
**Output:** false
**Explanation:** Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.

**Example 2:**

**Input:** nums = [1,5,233,7]
**Output:** true
**Explanation:** Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

**Constraints:**

* `1 <= nums.length <= 20`
* `0 <= nums[i] <= 107`

# Approaches
## Brute-Force Recursion
This approach directly models the game using a recursive function. At each turn, a player has two choices: take the number from the start or the end of the remaining array. The function calculates the score difference that can be achieved by exploring both choices and assuming the opponent also plays optimally. The optimal choice for the current player is the one that maximizes their score relative to the opponent.
**Time:** O(2^n), where n is the number of elements in the array. For each subproblem, we make two recursive calls, leading to an exponential number of calls. · **Space:** O(n), for the recursion stack depth.
**Pros:** Simple to conceptualize and implement.; Directly translates the problem statement into code.
**Cons:** Highly inefficient due to exponential time complexity.; Recalculates the same subproblems multiple times, leading to a Time Limit Exceeded error on larger inputs (though it might pass for n <= 20).
### Explanation
We define a recursive function, let's call it `maxDiff(nums, i, j)`, which calculates the maximum score the current player can get over the opponent from the subarray `nums[i...j]`.
The logic is as follows:
- **Base Case:** If `i == j`, there's only one number left. The current player takes it, so the score difference is `nums[i]`.
- **Recursive Step:** If `i < j`, the current player can either:
  1.  Choose `nums[i]`: Their score increases by `nums[i]`. The turn passes to the other player for the subarray `nums[i+1...j]`. The other player will, in turn, achieve a score difference of `maxDiff(nums, i+1, j)`. From the current player's perspective, this is a loss of `maxDiff(nums, i+1, j)`. So, the net score difference for this choice is `nums[i] - maxDiff(nums, i+1, j)`.
  2.  Choose `nums[j]`: Similarly, the net score difference is `nums[j] - maxDiff(nums, i, j-1)`.
Since the current player plays optimally, they will choose the option that gives them a higher score difference. Therefore, `maxDiff(nums, i, j) = max(choice1, choice2)`.
The final answer is determined by calling `maxDiff(nums, 0, n-1)`. If this value is non-negative, it means Player 1 can secure a score greater than or equal to Player 2, so Player 1 wins.
```java
class Solution {
    public boolean predictTheWinner(int[] nums) {
        return maxDiff(nums, 0, nums.length - 1) >= 0;
    }

    private int maxDiff(int[] nums, int i, int j) {
        if (i == j) {
            return nums[i];
        }
        
        int scoreByTakingFirst = nums[i] - maxDiff(nums, i + 1, j);
        int scoreByTakingLast = nums[j] - maxDiff(nums, i, j - 1);
        
        return Math.max(scoreByTakingFirst, scoreByTakingLast);
    }
}
```
### Algorithm
- Define a recursive function `maxDiff(nums, i, j)`.
- Base case: If `i == j`, return `nums[i]`.
- Recursive step: Calculate the score from taking the first element: `score1 = nums[i] - maxDiff(nums, i + 1, j)`.
- Calculate the score from taking the last element: `score2 = nums[j] - maxDiff(nums, i, j - 1)`.
- Return `max(score1, score2)`.
- In the main function, call `maxDiff(nums, 0, nums.length - 1)` and check if the result is `>= 0`.

## Recursion with Memoization (Top-Down DP)
This approach optimizes the brute-force recursion by caching the results of subproblems. A 2D array, `memo`, is used to store the computed score differences for each subarray `(i, j)`. Before making a recursive call for a subproblem, we check if its result is already in the cache. If so, we use the cached value; otherwise, we compute it, store it in the cache, and then return it. This technique is known as memoization or top-down dynamic programming.
**Time:** O(n^2), as each of the n*(n+1)/2 subproblems is solved exactly once. · **Space:** O(n^2), for the memoization table `memo` and the recursion stack.
**Pros:** Drastically improves performance over brute-force by avoiding re-computation.; Maintains the intuitive recursive structure.
**Cons:** Uses O(n^2) space for the memoization table.; May have a higher overhead than the iterative approach due to recursion.
### Explanation
The core recursive logic remains the same as the brute-force approach. The improvement comes from adding a memoization table, typically a 2D array `memo[n][n]`, to store the results of `maxDiff(i, j)`.
The table is initialized with a special value (e.g., `null` or `Integer.MIN_VALUE`) to indicate that a subproblem has not been solved yet.
The modified function `maxDiff(nums, i, j, memo)` works as follows:
1.  Check `memo[i][j]`. If it's not the initial value, it means we have already computed the result for this subproblem, so we return `memo[i][j]` directly.
2.  If `i == j`, this is a base case. We store `nums[i]` in `memo[i][i]` and return it.
3.  Otherwise, we compute the two possible outcomes recursively: `scoreByTakingFirst = nums[i] - maxDiff(nums, i + 1, j, memo)` and `scoreByTakingLast = nums[j] - maxDiff(nums, i, j - 1, memo)`.
4.  We take the maximum of these two outcomes, store it in `memo[i][j]`, and then return it.
This ensures that each subproblem `(i, j)` is solved only once.
```java
class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        Integer[][] memo = new Integer[n][n];
        return maxDiff(nums, 0, n - 1, memo) >= 0;
    }

    private int maxDiff(int[] nums, int i, int j, Integer[][] memo) {
        if (i == j) {
            return nums[i];
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        
        int scoreByTakingFirst = nums[i] - maxDiff(nums, i + 1, j, memo);
        int scoreByTakingLast = nums[j] - maxDiff(nums, i, j - 1, memo);
        
        memo[i][j] = Math.max(scoreByTakingFirst, scoreByTakingLast);
        return memo[i][j];
    }
}
```
### Algorithm
- Create a 2D array `memo[n][n]` and initialize it with a sentinel value (like `null`).
- Define a recursive function `maxDiff(nums, i, j, memo)`.
- If `memo[i][j]` is not the sentinel value, return it.
- Base case: If `i == j`, store `nums[i]` in `memo[i][i]` and return it.
- Recursive step: Calculate scores for both choices using recursive calls.
- Store the maximum score in `memo[i][j]` and return it.
- In the main function, call `maxDiff(nums, 0, n-1, memo)` and check if the result is `>= 0`.

## Iterative Dynamic Programming with 2D Array
This approach uses a bottom-up dynamic programming strategy to solve the problem without recursion. We build a 2D DP table, `dp[i][j]`, which stores the maximum score difference a player can achieve from the subarray `nums[i...j]`. We fill the table by iterating through subarray lengths, from 1 to `n`. For each length, we calculate the `dp` values for all possible subarrays of that length, using previously computed values for smaller subarrays.
**Time:** O(n^2), due to the nested loops iterating through all subarrays. · **Space:** O(n^2), for the 2D DP table.
**Pros:** Efficient with O(n^2) time complexity.; Avoids recursion overhead, which can be slightly faster than memoization in practice.
**Cons:** Requires O(n^2) space, which might be large for a very large `n` (though not an issue with the given constraints).
### Explanation
We use a 2D array `dp[n][n]`, where `dp[i][j]` stores the maximum score difference for the subarray `nums[i...j]`.
The table is filled based on the length of the subarray.
- **Initialization (length = 1):** For all subarrays of length 1, `dp[i][i] = nums[i]`. This is the base case where the player takes the only available element.
- **Iteration (length > 1):** We iterate `len` from 2 to `n`. For each `len`, we iterate through all possible start indices `i`. The end index `j` is `i + len - 1`. The value `dp[i][j]` is calculated using the same recurrence as before, but now we look up the values in our `dp` table instead of making recursive calls:
  `dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])`.
The term `dp[i+1][j]` represents the optimal score difference for the opponent on the subarray `nums[i+1...j]`, and `dp[i][j-1]` is for `nums[i...j-1]`. Since we fill the table for increasing lengths, `dp[i+1][j]` and `dp[i][j-1]` (which correspond to subarrays of length `len-1`) will have already been computed.
After filling the entire table, the answer for the whole array `nums[0...n-1]` is `dp[0][n-1]`. We return `true` if `dp[0][n-1] >= 0`.
```java
class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return true;
        }
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                int scoreByTakingFirst = nums[i] - dp[i + 1][j];
                int scoreByTakingLast = nums[j] - dp[i][j - 1];
                dp[i][j] = Math.max(scoreByTakingFirst, scoreByTakingLast);
            }
        }

        return dp[0][n - 1] >= 0;
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n][n]`.
- Initialize the diagonal: `dp[i][i] = nums[i]` for all `i`.
- Iterate for subarray length `len` from 2 to `n`.
- For each `len`, iterate for start index `i` from 0 to `n - len`.
- Calculate the end index `j = i + len - 1`.
- Compute `dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])`.
- After the loops, return `dp[0][n-1] >= 0`.

## Space-Optimized Iterative Dynamic Programming
This approach optimizes the space complexity of the bottom-up DP solution. Observing the recurrence relation `dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])`, we see that to compute a row `i` of the DP table, we only need the values from the row `i+1` and the previously computed values in the current row `i`. This dependency allows us to reduce the 2D DP table to a 1D array, bringing the space complexity down from O(n^2) to O(n).
**Time:** O(n^2), due to the nested loops. · **Space:** O(n), for the 1D DP array.
**Pros:** Most efficient approach in terms of space.; Maintains the efficient O(n^2) time complexity.
**Cons:** The logic for the iteration order can be less intuitive to derive compared to the 2D DP approach.
### Explanation
Instead of a 2D `dp` table, we use a 1D array, say `dp[n]`. We can iterate through the subproblems in a way that allows us to reuse this single array. The key is to iterate `i` from `n-1` down to `0`, and for each `i`, iterate `j` from `i` to `n-1`.
In this setup, `dp[j]` will store the result for the subarray ending at `j` that starts at the current `i`.
The update rule becomes `dp[j] = max(nums[i] - dp[j], nums[j] - dp[j-1])`.
Let's trace the update for `dp[j]`:
- `nums[i] - dp[j]`: Here, `dp[j]` still holds the value from the previous outer loop iteration (for `i+1`), which corresponds to `dp[i+1][j]` in the 2D version.
- `nums[j] - dp[j-1]`: Here, `dp[j-1]` has already been updated in the current inner loop iteration, so it holds the value for `dp[i][j-1]`.
This clever iteration order allows us to correctly compute all required values using only one array.
The final answer, the score difference for the entire array `nums[0...n-1]`, will be stored in `dp[n-1]` at the end of the process.
```java
class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    dp[i] = nums[i];
                } else {
                    int scoreByTakingFirst = nums[i] - dp[j];
                    int scoreByTakingLast = nums[j] - dp[j - 1];
                    dp[j] = Math.max(scoreByTakingFirst, scoreByTakingLast);
                }
            }
        }

        return dp[n - 1] >= 0;
    }
}
```
### Algorithm
- Create a 1D DP array `dp[n]`.
- Iterate `i` from `n - 1` down to `0`.
- Inside, iterate `j` from `i` to `n - 1`.
- If `i == j`, set `dp[i] = nums[i]` (or `dp[j] = nums[j]` since `i==j`).
- Otherwise, update `dp[j]` using the recurrence: `dp[j] = max(nums[i] - dp[j], nums[j] - dp[j-1])`.
- After the loops, the result for the whole array is in `dp[n-1]`.
- Return `dp[n-1] >= 0`.

# Solutions
### Java

```java
class Solution {
public
  boolean PredictTheWinner(int[] nums) {
    int n = nums.length;
    int[][] f = new int[n][n];
    for (int i = 0; i < n; ++i) {
      f[i][i] = nums[i];
    }
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = Math.max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);
      }
    }
    return f[0][n - 1] >= 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool PredictTheWinner(vector<int> &nums) {
    int n = nums.size();
    int f[n][n];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; ++i) {
      f[i][i] = nums[i];
    }
    for (int i = n - 2; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);
      }
    }
    return f[0][n - 1] >= 0;
  }
};

```

### Python

```python
class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool: n = len(nums) f = [[0] * n for _ in range(n)] for i, x in enumerate(nums): f[i][i] = x for i in range(n - 2, - 1, - 1): for j in range(i + 1, n): f[i][j] = max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]) return f[0][n - 1] >= 0

```