Skip to main content

486. Predict the Winner

medium

Two players pick numbers from either end of an array, both playing optimally. Decide whether player 1 wins or ties. Same interval-DP recurrence as Stone Game; Predict the Winner is the version that allows the player count to be odd.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 10^7

Examples

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 player 1 can win.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Interval DP on score difference. dp[i][j] = best (current player - opponent) score on nums[i..j].

Hint 2

dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]).

Hint 3

Return dp[0][n-1] >= 0. The >= covers the 'tie counts as win for player 1' rule.

Hint 4

Fill by increasing interval length, base case dp[i][i] = nums[i].

Solution approach

Reveal approach

Interval DP on score difference. dp[i][j] is the maximum (current player minus opponent) score the player to move can achieve on nums[i..j]. If they pick nums[i], they gain nums[i] and the opponent optimally plays the suffix, contributing dp[i+1][j] from their perspective; flip the sign so the value to the current player is nums[i] - dp[i+1][j]. Similarly for picking nums[j]. So dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]). Base: dp[i][i] = nums[i]. Fill in increasing interval length. Return dp[0][n-1] >= 0 — the 'tie counts as a win for player 1' rule is the >= rather than >. Memoized top-down recursion is equivalent.

Complexity

Time
O(n^2)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • interval-dp
  • game-theory

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Adobe

Practice these live with InterviewChamp.AI

Drill Predict the Winner and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →