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] <= 107This 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.
Java
C++
C
JavaScript
C#
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.
Java
C++
C
JavaScript
C#
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².
| 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. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,125 views views
Watch 9 more video solutions →Practice Predict the Winner with our built-in code editor and test cases.
Practice on FleetCode