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 <= 200 <= nums[i] <= 107Problem Overview: You get an integer array where two players alternately pick numbers from either end. Each player tries to maximize their final score. The goal is to determine whether Player 1 can guarantee a win (or tie) assuming both players play optimally.
Approach 1: Recursive Game Simulation with Memoization (Time: O(n^2), Space: O(n^2))
The key observation: instead of tracking absolute scores, track the score difference the current player can achieve over the opponent. If you pick nums[left], the opponent then plays optimally on the remaining subarray (left+1, right). The resulting difference becomes nums[left] - solve(left+1, right). Similarly for picking nums[right]. The optimal move is the maximum of these two choices.
This forms a classic recursion problem with overlapping subproblems. Use a 2D memo table dp[left][right] to store the best score difference for each subarray. Each state represents the best outcome the current player can enforce from that range. Memoization reduces the exponential search tree to O(n^2) states.
Approach 2: Bottom-Up Dynamic Programming (Time: O(n^2), Space: O(n^2))
The recursive relation can be converted into iterative dynamic programming. Define dp[i][j] as the maximum score difference the current player can achieve from subarray nums[i..j]. For a single element, dp[i][i] = nums[i] since the player takes the only number.
Expand intervals by length. For each range (i, j), compute dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]). This represents choosing either end and subtracting the opponent's optimal response. After filling the table, check dp[0][n-1] >= 0. A non‑negative difference means Player 1 can at least tie.
This formulation highlights the game theory structure of the problem. Every move maximizes the player's advantage while assuming the opponent also plays optimally.
Recommended for interviews: The memoized recursive solution communicates the game-theory insight clearly and is often the fastest to implement during interviews. The bottom-up dynamic programming version demonstrates stronger mastery of state transitions and iterative DP construction. Interviewers usually expect the O(n^2) DP insight rather than brute-force recursion.
This approach involves using recursion to explore all possible decisions by each player. With each choice, the players reduce the size of the array by selecting an element from either the start or end. Memoization is used to store intermediate results to minimize computational overhead by avoiding repeated calculations.
This solution defines a helper function calculate(i, j) which returns the best possible score a player can achieve from the subarray nums[i..j]. The player picks either the start or the end of the subarray. The opponent then plays optimally on the remaining subarray.
The recursive formula is max(nums[i] - calculate(i+1, j), nums[j] - calculate(i, j-1)), where the player's score is reduced by the opponent's optimal score. Memoization stores the results of calculate(i, j) calls to avoid recomputation.
Time Complexity: O(n²) - Each state (i, j) is computed once.
Space Complexity: O(n²) - Intermediate results are stored in the memoization table.
This approach utilizes dynamic programming to solve the problem iteratively. Instead of recursion, it fills up a DP table where each entry represents the best possible score difference a player can achieve for a subarray defined by its boundaries.
The Python solution involves initializing a 2D array dp where dp[i][j] stores the maximum score difference a player can achieve for nums[i...j]. We fill this table bottom-up, considering all possibilities by iterating over lengths of subarrays and their starting indices.
Time Complexity: O(n²) - The table is filled once for every distinct range.
Space Complexity: O(n²) - The DP table consumes space proportional to n².
We design a function dfs(i, j), which represents the maximum difference in scores between the current player and the other player from the i-th number to the j-th number. The answer is dfs(0, n - 1) geq 0.
The function dfs(i, j) is calculated as follows:
i > j, it means there are no numbers left, so the current player cannot take any points, and the difference is 0, i.e., dfs(i, j) = 0.i-th number, the difference in scores between the current player and the other player is nums[i] - dfs(i + 1, j). If they choose the j-th number, the difference in scores between the current player and the other player is nums[j] - dfs(i, j - 1). The current player will choose the option with the larger difference, so dfs(i, j) = max(nums[i] - dfs(i + 1, j), nums[j] - dfs(i, j - 1)).Finally, we only need to check if dfs(0, n - 1) geq 0.
To avoid repeated calculations, we can use memoization. We use an array f to record all the values of dfs(i, j). When the function is called again, we can directly retrieve the answer from f without recalculating it.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.
We can also use dynamic programming. Define f[i][j] to represent the maximum score difference the current player can achieve in the range nums[i..j]. The final answer is f[0][n - 1] geq 0.
Initially, f[i][i] = nums[i], because with only one number, the current player can only take that number, and the score difference is nums[i].
Consider f[i][j] where i < j, there are two cases:
nums[i], the remaining numbers are nums[i + 1..j], and it is the other player's turn. So, f[i][j] = nums[i] - f[i + 1][j].nums[j], the remaining numbers are nums[i..j - 1], and it is the other player's turn. So, f[i][j] = nums[j] - f[i][j - 1].Therefore, the state transition equation is f[i][j] = max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]).
Finally, we only need to check if f[0][n - 1] geq 0.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.
Similar problem:
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(n²) - Each state |
| Dynamic Programming Approach | Time Complexity: O(n²) - The table is filled once for every distinct range. |
| Memoization Search | — |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Game Simulation (Brute Force) | O(2^n) | O(n) | Conceptual understanding of the game tree and decision process |
| Recursion with Memoization | O(n^2) | O(n^2) | Top-down implementation that is easy to write during interviews |
| Bottom-Up Dynamic Programming | O(n^2) | O(n^2) | Preferred when converting recursion to iterative DP for predictable performance |
Predict the Winner || LEETCODE 486 || LEETCODE DYNAMIC PROGRAMMING || GAME THEORY • code Explainer • 19,167 views views
Watch 9 more video solutions →Practice Predict the Winner with our built-in code editor and test cases.
Practice on FleetCode