LeetCode 486: Predict the Winner

Problem Restatement

We are given an integer array nums.

Two players play a game with this array.

Player 1 moves first. On each turn, the current player must take one number from either end of the array. That means the player may take either the leftmost number or the rightmost number.

The chosen number is added to that player’s score, and the number is removed from the array.

Both players play optimally.

Return true if Player 1 can win. A tie also counts as a win for Player 1. The official statement specifies that equal scores should also return true, and the constraints are 1 <= nums.length <= 20 and 0 <= nums[i] <= 10^7.

Input and Output

Function shape:

def predictTheWinner(nums: list[int]) -> bool:
    ...

Examples

Example 1:

nums = [1, 5, 2]

Player 1 can choose either 1 or 2.

If Player 1 takes 1, Player 2 takes 5, then Player 1 gets 2.

Final scores:

Player 1 = 1 + 2 = 3
Player 2 = 5

If Player 1 takes 2, Player 2 still takes 5, then Player 1 gets 1.

Final scores:

Player 1 = 2 + 1 = 3
Player 2 = 5

Player 1 cannot win or tie.

Answer:

False

Example 2:

nums = [1, 5, 233, 7]

Player 1 can take 1.

Then Player 2 must choose between 5 and 7.

No matter which one Player 2 chooses, Player 1 can take 233.

Final result can be:

Player 1 = 1 + 233 = 234
Player 2 = 7 + 5 = 12

Player 1 wins.

Answer:

True

First Thought: Simulate Every Game

A direct solution is to try every possible sequence of moves.

At each turn, the current player has two choices:

1. Take the left number.
2. Take the right number.

This forms a recursion tree.

For example:

nums = [1, 5, 2]

Player 1 can take 1 or 2.

Then Player 2 also chooses from the remaining ends.

This approach can find the answer, but it repeats the same subproblems many times.

Problem With Plain Recursion

The array length can be up to 20.

Each move branches into two choices, so plain recursion can take roughly:

O(2^n)

That is avoidable because the game state is fully described by the remaining interval:

left index, right index

The same interval may be reached through different previous choices.

So we use dynamic programming.

Key Insight

Instead of tracking both players’ scores separately, track the score difference from the current player’s point of view.

Define:

dp(left, right)

as the maximum score difference the current player can achieve over the other player using only:

nums[left:right + 1]

A positive value means the current player can finish ahead from this subarray.

A zero value means the current player can tie.

A negative value means the current player falls behind.

On the current turn, there are two choices.

If the player takes nums[left], the opponent becomes the current player for the remaining subarray left + 1 to right.

The opponent can then achieve:

dp(left + 1, right)

against us.

So our net score difference from taking left is:

nums[left] - dp(left + 1, right)

Similarly, taking right gives:

nums[right] - dp(left, right - 1)

We choose the better option:

dp(left, right) = max(
    nums[left] - dp(left + 1, right),
    nums[right] - dp(left, right - 1)
)

Algorithm

Use recursion with memoization.

For dp(left, right):

1. If left == right, only one number remains, so return nums[left].
2. Compute the result if taking the left number.
3. Compute the result if taking the right number.
4. Return the larger score difference.

At the end, Player 1 can win or tie if:

dp(0, len(nums) - 1) >= 0

Correctness

The function dp(left, right) represents the best score difference the current player can force from the subarray nums[left:right + 1].

If only one number remains, the current player takes it, and the score difference is exactly that number.

For a longer interval, the current player has exactly two legal moves: take the left end or take the right end.

If the current player takes the left value, they gain nums[left]. The opponent then becomes the current player on the remaining interval. Since dp(left + 1, right) is the best score difference the opponent can force from there, the original player’s final advantage is nums[left] - dp(left + 1, right).

The same reasoning gives nums[right] - dp(left, right - 1) for taking the right value.

The current player plays optimally, so the correct value is the maximum of those two choices.

By induction on interval length, dp(left, right) is correct for every interval. Therefore, dp(0, n - 1) is the best final score difference Player 1 can force for the whole game. Player 1 wins or ties exactly when this value is at least zero.

Complexity

The recursion depth is O(n).

Implementation

from functools import cache

class Solution:
    def predictTheWinner(self, nums: list[int]) -> bool:
        @cache
        def dp(left: int, right: int) -> int:
            if left == right:
                return nums[left]

            take_left = nums[left] - dp(left + 1, right)
            take_right = nums[right] - dp(left, right - 1)

            return max(take_left, take_right)

        return dp(0, len(nums) - 1) >= 0

Code Explanation

The memoized function stores the best score difference for each interval:

@cache
def dp(left: int, right: int) -> int:

The base case is one remaining number:

if left == right:
    return nums[left]

If we take the left number, the opponent controls the remaining interval:

take_left = nums[left] - dp(left + 1, right)

If we take the right number, the same logic applies:

take_right = nums[right] - dp(left, right - 1)

We choose the better move:

return max(take_left, take_right)

Finally, Player 1 can win or tie if the final difference is non-negative:

return dp(0, len(nums) - 1) >= 0

Bottom-Up Implementation

The same recurrence can be written iteratively.

Let dp[i][j] mean the best score difference the current player can force from nums[i:j + 1].

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 left in range(n - length + 1):
                right = left + length - 1

                take_left = nums[left] - dp[left + 1][right]
                take_right = nums[right] - dp[left][right - 1]

                dp[left][right] = max(take_left, take_right)

        return dp[0][n - 1] >= 0

Testing

def run_tests():
    s = Solution()

    assert s.predictTheWinner([1, 5, 2]) is False
    assert s.predictTheWinner([1, 5, 233, 7]) is True
    assert s.predictTheWinner([1]) is True
    assert s.predictTheWinner([1, 1]) is True
    assert s.predictTheWinner([2, 4, 55, 6, 8]) is False
    assert s.predictTheWinner([0, 0, 0]) is True

    print("all tests passed")

run_tests()

Test meaning: