Predict the Winner

Medium
873.

Predict the Winner

Predict the Winner is a medium coding problem on arrays, dynamic programming and recursion, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var predictTheWinner = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Predict the Winner — Solution in Python, Java & C++

Predict the Winner solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Predict the Winner is a medium coding problem on arrays, dynamic programming and recursion, asked in Amazon, Google and Adobe interviews.

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

Hints for Predict the Winner

  1. Hint 1

    Track the score difference from the perspective of whoever is about to move, not two separate scores.

  2. Hint 2

    dp[i][j] is the best difference the current player can force on nums[i … j].

  3. Hint 3

    Taking an end flips the perspective: dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]).

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

  1. Base case: a single element gives the mover that value.
  2. Fill intervals by increasing length with dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]).
  3. 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

Java

public static boolean predictTheWinner(int[] nums) {
    int n = nums.length;
    long[][] dp = new long[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = nums[i];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1] >= 0;
}

C++

bool predictTheWinner(vector<int>& nums) {
    int n = (int) nums.size();
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = nums[i];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = max((long long) nums[i] - dp[i + 1][j], (long long) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming