MediumArrayMathDynamic ProgrammingRecursionGame Theory

Predict the Winner

1 approach, code in every language

You are given an integer array nums. Two players take turns, and Player 1 moves first. On each turn a player takes either the first or the last element of the remaining array and adds its value to their own running score; the chosen element is then removed.

When no elements remain, the game ends. Assuming both players play optimally to maximize their own score, return true if Player 1 can finish with a score greater than or equal to Player 2, and false otherwise. If the scores are tied, Player 1 is considered the winner.

Example 1

Input: nums = [1,5,2]

Output: false

Whether Player 1 first takes the 1 or the 2, Player 2 can respond so that Player 2 captures the 5, ending with a strictly higher total. Player 1 cannot force at least a tie.

Example 2

Input: nums = [1,5,233,7]

Output: true

Player 1 can secure the large 233 by playing the ends optimally, guaranteeing a final score that is at least as high as Player 2.

Constraints

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

Interval DP on Score Margin

Compute, for every subarray, the best score margin the current player can force, then check the sign of the full-array result.

Loading animation…

Intuition

Instead of tracking both players' scores separately, it is cleaner to track a single quantity: the margin by which the player to move can beat the other player on a given subarray. Let dp[i][j] be that best margin over nums[i..j]. If the current player takes nums[i], they gain nums[i] and then face dp[i+1][j] from the opponent's perspective, which counts against them, so this option is worth nums[i] - dp[i+1][j]. Taking nums[j] is symmetrically worth nums[j] - dp[i][j-1]. The current player chooses the larger of the two, and a single-element range simply yields that element as the margin. Player 1 can guarantee at least a tie exactly when dp[0][n-1] is non-negative.

Algorithm walkthrough

1Set dp[i][i] = nums[i]: with one element the current player takes it and leads by that amount.
2Process subarrays in order of increasing length so shorter ranges are ready before longer ones.
3For range i..j, taking the left end is worth nums[i] - dp[i+1][j].
4Taking the right end is worth nums[j] - dp[i][j-1]; assign dp[i][j] the maximum of the two options.
5The value dp[0][n-1] is Player 1's optimal margin over the whole array.
6Return true when that margin is at least zero, since a tie counts as a Player 1 win.

Implementation

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        for length in range(2, n + 1):
            for i in range(0, n - length + 1):
                j = i + length - 1
                take_left = nums[i] - dp[i + 1][j]
                take_right = nums[j] - dp[i][j - 1]
                dp[i][j] = max(take_left, take_right)
        return dp[0][n - 1] >= 0

Time

O(n^2)

Space

O(n^2)

Every subarray is evaluated once in O(1); the table can be compressed to a single row of size n if memory is a concern.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Bundle Claim Duel is our own problem on the technique behind Predict the Winner: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free