486. Predict the Winner
Model: qwen3.5:9b
Topics: Dynamic Programming,Minimax
FAANG asked: 1
Acceptance rate: 49.0%
Problem Breakdown
We are given a list of non-negative integers representing scores available in a game played by two players, Player 1 and Player 2. They take turns picking numbers from either the left or right end of the array until all numbers are picked. Both players play optimally to maximize their own total score.
Goal: Determine if Player 1 can guarantee that their final score is greater than or equal to Player 2’s score (since a tie counts as a win for P1).
- Input: A list of integers
nums. - Output: Boolean (
Trueif P1 wins/ties, elseFalse). - Constraints: Array length is small (), scores are non-negative.
- Key Insight: This is a zero-sum game scenario regarding the difference in scores. We don’t necessarily need to track absolute sums for both players; we just need to know if P1 can secure a score difference .
Intuition
If I were solving this out loud, my first thought would be recursion with backtracking: “At each step, Player 1 chooses left or right. Then it’s Player 2’s turn.” However, since both players play optimally to maximize their own gain (which minimizes the opponent’s relative gain), we need a way to model optimal responses.
A pure recursive solution would explore every possible game path. The state is defined by which elements remain available (left_index and right_index). While allows for exponential time complexity () technically, this approach has overlapping subproblems (e.g., the remaining array [i+1...j] might be reached via different choices).
The key insight is to use Dynamic Programming. Instead of tracking absolute scores, we track the maximum score difference (current_player_score - opponent_score) achievable from a specific range. If it’s my turn on subarray nums[i..j], I want to maximize (my_pick) - (opponent_best_diff_on_remaining_range).
Approach
We will use bottom-up Dynamic Programming with an table, where dp[i][j] represents the maximum score difference Player 1 can achieve over Player 2 for the subarray from index i to j, assuming it is currently their turn.
Recurrence Relation:
For a range [i, j]:
- Option A (Pick Left): Take
nums[i]. The opponent will then play optimally on[i+1, j], achieving a difference ofdp[i+1][j]relative to them. Since it’s zero-sum logic for the remaining game, my net gain isnums[i] - dp[i+1][j]. - Option B (Pick Right): Take
nums[j]. The opponent plays on[i, j-1], achieving differencedp[i][j-1]. My net gain isnums[j] - dp[i][j-1].
Formula:
dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
We fill the table by iterating through subarray lengths from 1 to . The base case is when i == j, where there’s only one element left, so the difference is simply that value. Finally, we check if dp[0][n-1] >= 0.
Complexity Analysis
- Time Complexity: . We fill an table, and each cell takes constant time to compute (). Given the constraint , this is extremely fast. Even for larger inputs (e.g., up to a few hundred), it remains efficient enough.
- Space Complexity: . We store an DP table. This can be optimized to using space optimization techniques, but given the constraints and clarity of explanation, the 2D array is preferred for readability in this context.
Solution
def predictTheWinner(nums):
n = len(nums)
# dp[i][j] stores the max score difference (P1 - P2)
# Player 1 can achieve from subarray nums[i...j].
dp = [[0 for _ in range(n)] for _ in range(n)]
# Base case: Subarrays of length 1.
# If only one element remains, the current player takes it.
# The difference is simply that value (since opponent gets 0 from this step).
for i in range(n):
dp[i][i] = nums[i]
# Fill table by subarray length starting from 2 up to n
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
# If we pick left (nums[i]), opponent plays on [i+1...j]
# Their best diff is dp[i+1][j]. We subtract that from our gain.
option_left = nums[i] - dp[i+1][j]
# If we pick right (nums[j]), opponent plays on [i...j-1]
option_right = nums[j] - dp[i][j-1]
# Current player chooses the move that maximizes their relative score.
dp[i][j] = max(option_left, option_right)
# If the difference for the full array is >= 0, P1 wins or ties.
return dp[0][n - 1] >= 0
Edge Cases Handled
- Single Element Array: The loop logic handles
length=2onwards; base case fills diagonal with single values. If input[5], returns True (P1 takes it, P2 gets nothing). - Tie Condition: Since we return
dp[0][n-1] >= 0, a score difference of exactly zero is treated as a win for Player 1 per the problem statement (“If the scores… are equal, then player 1 is still the winner”). - Empty Input: Constraints state length , but if
numswere empty, code would return False (or crash depending on implementation). Given constraints , this isn’t triggered. - Large Values: Python handles large integers automatically; overflow is not a concern here as per standard LeetCode environment behavior for these constraints.