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.
1#include <stdio.h>
2#include <limits.h>
3
4int calculate(int* nums, int i, int j, int** memo)
This solution leverages recursion with memoization. It involves calculating the best score a player can secure optimally by recursively deciding whether to pick from the beginning or the end of the array. The results for each state (combination of i and j) of the nums array are stored in a memoization table to avoid redundant calculations.
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.
This Java solution constructs a 2D DP table where dp[i][j] represents the maximum advantageous score a player can ensure from the subarray nums[i...j]. Filling starts from single elements and progresses to larger subarrays, comparing feasible moves.