Predict the Winner
MedPrompt
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] <= 107
Approaches
4 approaches with complexity analysis and trade-offs.
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).
Algorithm
- Create a 1D DP array
dp[n]. - Iterate
ifromn - 1down to0. - Inside, iterate
jfromiton - 1. - If
i == j, setdp[i] = nums[i](ordp[j] = nums[j]sincei==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.
Walkthrough
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 (fori+1), which corresponds todp[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 fordp[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 arraynums[0...n-1], will be stored indp[n-1]at the end of the process.
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; }}Complexity
Time
O(n^2), due to the nested loops.
Space
O(n), for the 1D DP array.
Trade-offs
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.
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.
Algorithm
- Create a 2D DP table
dp[n][n]. - Initialize the diagonal:
dp[i][i] = nums[i]for alli. - Iterate for subarray length
lenfrom 2 ton. - For each
len, iterate for start indexifrom 0 ton - 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.
Walkthrough
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
lenfrom 2 ton. For eachlen, we iterate through all possible start indicesi. The end indexjisi + len - 1. The valuedp[i][j]is calculated using the same recurrence as before, but now we look up the values in ourdptable instead of making recursive calls:dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]). The termdp[i+1][j]represents the optimal score difference for the opponent on the subarraynums[i+1...j], anddp[i][j-1]is fornums[i...j-1]. Since we fill the table for increasing lengths,dp[i+1][j]anddp[i][j-1](which correspond to subarrays of lengthlen-1) will have already been computed. After filling the entire table, the answer for the whole arraynums[0...n-1]isdp[0][n-1]. We returntrueifdp[0][n-1] >= 0.
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; }}Complexity
Time
O(n^2), due to the nested loops iterating through all subarrays.
Space
O(n^2), for the 2D DP table.
Trade-offs
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).
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.
Algorithm
- Define a recursive function
maxDiff(nums, i, j). - Base case: If
i == j, returnnums[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.
Walkthrough
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 isnums[i]. - Recursive Step: If
i < j, the current player can either:- Choose
nums[i]: Their score increases bynums[i]. The turn passes to the other player for the subarraynums[i+1...j]. The other player will, in turn, achieve a score difference ofmaxDiff(nums, i+1, j). From the current player's perspective, this is a loss ofmaxDiff(nums, i+1, j). So, the net score difference for this choice isnums[i] - maxDiff(nums, i+1, j). - Choose
nums[j]: Similarly, the net score difference isnums[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 callingmaxDiff(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.
- Choose
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); }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Create a 2D array
memo[n][n]and initialize it with a sentinel value (likenull). - 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, storenums[i]inmemo[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.
Walkthrough
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:
- Check
memo[i][j]. If it's not the initial value, it means we have already computed the result for this subproblem, so we returnmemo[i][j]directly. - If
i == j, this is a base case. We storenums[i]inmemo[i][i]and return it. - Otherwise, we compute the two possible outcomes recursively:
scoreByTakingFirst = nums[i] - maxDiff(nums, i + 1, j, memo)andscoreByTakingLast = nums[j] - maxDiff(nums, i, j - 1, memo). - 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.
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]; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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] >= 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.