Watch 10 video solutions for Predict the Winner, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by code Explainer has 19,167 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |