LeetCode 486 - Predict the Winner

The problem describes a two-player game played on an integer array. Players alternate turns, and during each turn a player may only take a number from one of the two ends of the array. The chosen value is added to that player's score, and the element is removed from the array.

leetcodemediumarraymathdynamic-programmingrecursiongame-theory

LeetCode Problem 486

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Recursion, Game Theory

Solution

Problem Understanding

The problem describes a two-player game played on an integer array. Players alternate turns, and during each turn a player may only take a number from one of the two ends of the array. The chosen value is added to that player's score, and the element is removed from the array. The game continues until all elements have been taken.

The goal is to determine whether Player 1 can guarantee a win assuming both players play optimally. In this problem, a tie is also considered a win for Player 1.

The input is an integer array nums, where each element represents a score value available to pick. Since players may only choose from the leftmost or rightmost remaining element, the game state is completely determined by the current subarray.

The output is a boolean value:

  • Return true if Player 1 can end the game with a score greater than or equal to Player 2's score.
  • Return false if Player 2 can force Player 1 to lose.

The constraints are relatively small:

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

The small array length is an important clue. A naive recursive solution that explores all possibilities is technically feasible for small inputs, but it still grows exponentially and becomes inefficient as the length approaches 20. This suggests that dynamic programming or memoization is the intended optimization.

Several edge cases are important to consider:

  • Arrays with only one element. Player 1 immediately takes the only number and wins.
  • Arrays where both players can end with equal scores. The problem explicitly states that ties count as wins for Player 1.
  • Arrays with repeated values, where many game paths appear equivalent.
  • Arrays where a greedy strategy fails. Choosing the larger end immediately does not always lead to the optimal final outcome.
  • Arrays containing zeros, where score differences become subtle.

The key challenge is that both players play optimally, meaning every decision must account for the opponent making the best possible response.

Approaches

Brute Force Approach

The brute-force approach recursively simulates every possible game state.

At any point, the current player has two choices:

  • Take the leftmost number
  • Take the rightmost number

After making a choice, the opponent recursively plays optimally on the remaining subarray.

A straightforward implementation computes the maximum total score Player 1 can achieve by exploring every possible sequence of moves. Since each level of recursion branches into two possibilities, the total number of states grows exponentially.

This approach is correct because it exhaustively evaluates all valid game paths and always assumes optimal play from both sides. However, it repeatedly recalculates the same subproblems. For example, the same subarray may be evaluated many times from different recursive paths.

The time complexity becomes approximately O(2^n), which is inefficient even for moderately sized inputs.

Optimal Dynamic Programming Approach

The key insight is that the game is zero-sum.

Instead of tracking the absolute scores of both players separately, we can track the score difference between the current player and the opponent.

Define:

  • dp(left, right) = maximum score difference the current player can achieve over the opponent using the subarray nums[left:right+1]

If the current player picks the left value:

  • They gain nums[left]
  • The opponent then becomes the current player for the remaining subarray
  • The opponent's advantage is dp(left + 1, right)

So the resulting score difference becomes:

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

Similarly, if the current player picks the right value:

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

The current player chooses the better option:

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

If the final score difference for the full array is non-negative, then Player 1 can guarantee at least a tie.

This transforms the exponential recursive solution into a dynamic programming problem with overlapping subproblems.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively explores every possible game sequence
Optimal O(n^2) O(n^2) Uses memoization or DP to reuse subproblem results

Algorithm Walkthrough

  1. Define a recursive function dfs(left, right) that returns the maximum score difference the current player can achieve over the opponent for the subarray from index left to right.
  2. Handle the base case first. If left == right, only one number remains, so the current player takes it immediately. The score difference is simply:
nums[left]
  1. For larger subarrays, consider the two available moves.

If the current player chooses the left element:

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

The subtraction is important because after the move, the opponent becomes the current player. Whatever advantage the opponent gains must reduce the current player's final advantage. 4. Similarly, if the current player chooses the right element:

nums[right] - dfs(left, right - 1)
  1. Choose the move that maximizes the current player's score difference.
max(left_choice, right_choice)
  1. Use memoization to store previously computed (left, right) states. Without memoization, many subarrays would be recomputed repeatedly.
  2. Start the recursion with the full array:
dfs(0, n - 1)
  1. If the returned score difference is greater than or equal to zero, Player 1 can guarantee at least a tie, so return true.

Why it works

The algorithm works because every game state can be represented by a subarray and the identity of the current player. The recursive relation correctly models optimal play from both sides. Each player maximizes their own score difference while assuming the opponent also plays optimally. Since every subproblem is solved exactly once with memoization, the final result represents the true optimal outcome of the game.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)

        @lru_cache(None)
        def dfs(left: int, right: int) -> int:
            if left == right:
                return nums[left]

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

            return max(take_left, take_right)

        return dfs(0, n - 1) >= 0

The implementation begins by importing lru_cache, which provides memoization for the recursive function. Memoization is critical because many overlapping subproblems occur during recursion.

The dfs(left, right) function represents the maximum score difference the current player can achieve for the current subarray.

The base case handles subarrays of length one. If only one number remains, the current player must take it, so the score difference equals that number.

For larger subarrays, the function evaluates both valid moves:

  • Taking the leftmost number
  • Taking the rightmost number

After taking a number, the opponent plays optimally on the remaining subarray. Since dfs() returns the opponent's future advantage, that value is subtracted from the current player's gain.

The function returns the maximum of the two choices because the current player always chooses the optimal move.

Finally, the algorithm evaluates the full array and checks whether the resulting score difference is non-negative. A non-negative value means Player 1 can secure at least a tie.

Go Solution

package main

func predictTheWinner(nums []int) bool {
	n := len(nums)

	memo := make([][]int, n)
	visited := make([][]bool, n)

	for i := 0; i < n; i++ {
		memo[i] = make([]int, n)
		visited[i] = make([]bool, n)
	}

	var dfs func(int, int) int

	dfs = func(left int, right int) int {
		if left == right {
			return nums[left]
		}

		if visited[left][right] {
			return memo[left][right]
		}

		takeLeft := nums[left] - dfs(left+1, right)
		takeRight := nums[right] - dfs(left, right-1)

		if takeLeft > takeRight {
			memo[left][right] = takeLeft
		} else {
			memo[left][right] = takeRight
		}

		visited[left][right] = true

		return memo[left][right]
	}

	return dfs(0, n-1) >= 0
}

The Go implementation follows the same dynamic programming strategy as the Python solution, but memoization is implemented manually.

Since Go does not provide a built-in memoization decorator like Python's lru_cache, two 2D slices are used:

  • memo stores computed results
  • visited tracks whether a state has already been computed

This avoids ambiguity because a valid score difference could also be zero.

Go slices are used instead of fixed arrays because the input size is dynamic. Integer overflow is not a concern because the maximum total score is well within Go's integer range.

Worked Examples

Example 1

nums = [1,5,2]

We compute:

dfs(0, 2)
State Calculation Result
dfs(2,2) only 2 remains 2
dfs(1,1) only 5 remains 5
dfs(0,0) only 1 remains 1
dfs(1,2) max(5 - 2, 2 - 5) 3
dfs(0,1) max(1 - 5, 5 - 1) 4
dfs(0,2) max(1 - 3, 2 - 4) -2

Final result:

dfs(0,2) = -2

A negative value means Player 1 loses by 2 points if both play optimally.

Output:

false

Example 2

nums = [1,5,233,7]

We compute recursively.

State Calculation Result
dfs(3,3) 7 7
dfs(2,2) 233 233
dfs(1,1) 5 5
dfs(0,0) 1 1
dfs(2,3) max(233 - 7, 7 - 233) 226
dfs(1,2) max(5 - 233, 233 - 5) 228
dfs(0,1) max(1 - 5, 5 - 1) 4
dfs(1,3) max(5 - 226, 7 - 228) -221
dfs(0,2) max(1 - 228, 233 - 4) 229
dfs(0,3) max(1 - (-221), 7 - 229) 222

Final result:

dfs(0,3) = 222

Since the value is positive, Player 1 can guarantee victory.

Output:

true

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) There are n * n possible subarray states
Space O(n^2) Memoization stores one value for each subarray

The recursion considers every possible (left, right) pair exactly once because memoization prevents repeated computation. Since there are n^2 distinct subarrays, the total time complexity is O(n^2).

The memoization table also stores one value per subarray, requiring O(n^2) space. The recursion stack adds at most O(n) additional space, but the memo table dominates overall memory usage.

Test Cases

from typing import List
from functools import lru_cache

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        @lru_cache(None)
        def dfs(left: int, right: int) -> int:
            if left == right:
                return nums[left]

            return max(
                nums[left] - dfs(left + 1, right),
                nums[right] - dfs(left, right - 1)
            )

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

solution = Solution()

assert solution.predictTheWinner([1, 5, 2]) is False  # provided example where player 1 loses
assert solution.predictTheWinner([1, 5, 233, 7]) is True  # provided example where player 1 wins

assert solution.predictTheWinner([10]) is True  # single element array
assert solution.predictTheWinner([1, 1]) is True  # tie counts as win
assert solution.predictTheWinner([0, 0, 0]) is True  # all zeros

assert solution.predictTheWinner([2, 4, 55, 6, 8]) is False  # non-greedy optimal play
assert solution.predictTheWinner([1, 3, 1]) is False  # small odd-length losing case
assert solution.predictTheWinner([1, 3, 7, 3]) is True  # balanced strategic case

assert solution.predictTheWinner([10000000, 1, 1, 10000000]) is True  # large values
assert solution.predictTheWinner([5, 5, 5, 5]) is True  # repeated equal values
Test Why
[1,5,2] Validates losing scenario
[1,5,233,7] Validates winning scenario
[10] Tests single-element base case
[1,1] Confirms tie handling
[0,0,0] Tests all-zero values
[2,4,55,6,8] Validates optimal strategy over greedy choice
[1,3,1] Tests small odd-length losing case
[1,3,7,3] Tests balanced strategic play
[10000000,1,1,10000000] Tests large integer values
[5,5,5,5] Tests repeated equal numbers

Edge Cases

A single-element array is the simplest possible input. Since Player 1 always moves first, they immediately take the only number and win. Recursive solutions can fail here if the base case is not handled correctly. The implementation explicitly checks left == right and returns the remaining number directly.

Arrays where both players end with equal scores are another important case. Many implementations mistakenly require Player 1 to have a strictly greater score. The problem states that ties count as wins for Player 1, so the final condition must be:

score_difference >= 0

rather than:

score_difference > 0

Cases where greedy selection fails are especially dangerous. For example:

[1, 5, 233, 7]

A naive greedy algorithm might always take the larger end value immediately, but optimal play often requires sacrificing short-term gain for a better future outcome. The dynamic programming solution avoids this issue by evaluating the full consequence of every move recursively.

Repeated values and zero-heavy arrays can also expose memoization bugs. Different recursive paths may produce identical states, and without caching the algorithm becomes exponentially slow. The memoized implementation guarantees that every subarray state is computed only once.