Predict the Winner — Medium Problem & Solution

Two players take turns picking a number from either end of nums, adding it to their score. Player 1 goes first and both play optimally.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Game Theory, Recursion
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two players take turns picking a number from either end of nums, adding it to their score. Player 1 goes first and both play optimally.

Return whether player 1 wins. A tie counts as a win for player 1.

Example 1

Input: nums = [1,5,2]
Output: false
Explanation: Whatever player 1 takes, player 2 can take the 5.

Example 2

Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 takes 1, then 233 becomes reachable.

Example 3

Input: nums = [2,2]
Output: true
Explanation: Both score 2, and a tie favours player 1.

Constraints

1 <= nums.length <= 20
0 <= nums[i] <= 10000000

How to solve Predict the Winner

Collapse the two scores into one number — the lead of the player to move. Then the recurrence is symmetric: whichever end you take, the opponent faces the remaining interval and their best lead is subtracted from yours.

Approach

Base case: a single element gives the mover that value.
Fill intervals by increasing length with dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]).
Player 1 wins when dp[0][n-1] >= 0.

Why it works

Both players optimise the same objective from their own side, so the game is zero-sum in the lead. Subtracting the opponent's best lead correctly models that their gain is your loss. The interval [i, j] is the only state that matters, since the numbers already taken never affect what remains.

Complexity

Time — O(n²)
Space — O(n²)

Pitfalls

Tracking both scores separately needs an extra dimension and is easy to get wrong.
A tie is a win for player 1, so the test is >= 0, not > 0.
The intervals must be filled by increasing length, or the subproblems are not ready.

Reference solution

Python

from typing import List

def predictTheWinner(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(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
    return dp[0][n - 1] >= 0

JavaScript

var predictTheWinner = function(nums) {
    var n = nums.length;
    var dp = [];
    for (var a = 0; a < n; a++) {
        var row = [];
        for (var b = 0; b < n; b++) row.push(0);
        dp.push(row);
    }
    for (var i = 0; i < n; i++) dp[i][i] = nums[i];
    for (var len = 2; len <= n; len++) {
        for (var s = 0; s + len - 1 < n; s++) {
            var e = s + len - 1;
            dp[s][e] = Math.max(nums[s] - dp[s + 1][e], nums[e] - dp[s][e - 1]);
        }
    }
    return dp[0][n - 1] >= 0;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue