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] <= 107The key idea in #486 Predict the Winner is to model the game as an optimal strategy problem between two players. Each player chooses a number from either end of the array and both aim to maximize their total score. Instead of tracking both players' scores separately, we can think in terms of the score difference the current player can achieve over the opponent.
A common approach uses dynamic programming with recursion (minimax idea). Define dp[l][r] as the maximum score difference the current player can achieve from the subarray nums[l...r]. The player can pick either the left or right value, after which the opponent will play optimally. Therefore, the player chooses the option that maximizes their advantage.
This approach can be implemented using top-down recursion with memoization or a bottom-up DP table. By storing results for subproblems, we avoid recomputation and efficiently determine whether the first player can secure a non-negative score difference.
The DP solution runs in O(n²) time since all subarray states are evaluated.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursion with Memoization (Game Theory DP) | O(n^2) | O(n^2) |
| Bottom-Up Dynamic Programming | O(n^2) | O(n^2) |
Ashish Pratap Singh
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.
Time Complexity: O(n²) - Each state (i, j) is computed once.
Space Complexity: O(n²) - Intermediate results are stored in the memoization table.
1def PredictTheWinner(nums):
2
3 def calculate(i, j):
4 if i == j:
5 return nums[i]
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.
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.
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².
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem are common in interviews at companies like Google, Amazon, and Meta. It tests understanding of dynamic programming, recursion, and game theory strategies where players make optimal decisions.
A 2D dynamic programming table or memoization cache is typically used. Each entry represents the best score difference achievable from a specific subarray range. This structure helps efficiently reuse results of overlapping subproblems.
Game theory helps model the interaction between two optimal players. Each move affects the opponent's future choices, so the algorithm evaluates the best outcome assuming the opponent also plays optimally.
The optimal approach uses dynamic programming with a minimax-style strategy. Instead of tracking both players' scores, it stores the maximum score difference a player can achieve from any subarray. This reduces repeated computation and ensures optimal decisions.
The C solution involves setting up a 2D dynamic programming table where dp[i][j] indicates the maximum difference of scores that results if the game begins with the subarray nums[i...j]. This table guides the decision making at each step.