Skip to main content
Talentd

Predict the Winner - Solution & Explanation

MediumArrayMathDynamic ProgrammingRecursion28 min readAsked at: Amazon, Microsoft, Cisco +3
Practice this problem

Problem Statement

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

 

Example 1:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.

Example 2:

Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

 

Constraints:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 107

Approach Overview

Problem Overview: You get an integer array where two players alternately pick numbers from either end. Each player tries to maximize their final score. The goal is to determine whether Player 1 can guarantee a win (or tie) assuming both players play optimally.

Approach 1: Recursive Game Simulation with Memoization (Time: O(n^2), Space: O(n^2))

The key observation: instead of tracking absolute scores, track the score difference the current player can achieve over the opponent. If you pick nums[left], the opponent then plays optimally on the remaining subarray (left+1, right). The resulting difference becomes nums[left] - solve(left+1, right). Similarly for picking nums[right]. The optimal move is the maximum of these two choices.

This forms a classic recursion problem with overlapping subproblems. Use a 2D memo table dp[left][right] to store the best score difference for each subarray. Each state represents the best outcome the current player can enforce from that range. Memoization reduces the exponential search tree to O(n^2) states.

Approach 2: Bottom-Up Dynamic Programming (Time: O(n^2), Space: O(n^2))

The recursive relation can be converted into iterative dynamic programming. Define dp[i][j] as the maximum score difference the current player can achieve from subarray nums[i..j]. For a single element, dp[i][i] = nums[i] since the player takes the only number.

Expand intervals by length. For each range (i, j), compute dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]). This represents choosing either end and subtracting the opponent's optimal response. After filling the table, check dp[0][n-1] >= 0. A non‑negative difference means Player 1 can at least tie.

This formulation highlights the game theory structure of the problem. Every move maximizes the player's advantage while assuming the opponent also plays optimally.

Recommended for interviews: The memoized recursive solution communicates the game-theory insight clearly and is often the fastest to implement during interviews. The bottom-up dynamic programming version demonstrates stronger mastery of state transitions and iterative DP construction. Interviewers usually expect the O(n^2) DP insight rather than brute-force recursion.

Approach 1: Recursive Approach with Memoization

This approach involves using recursion to explore all possible decisions by each player. With each choice, the players reduce the size of the array by selecting an element from either the start or end. Memoization is used to store intermediate results to minimize computational overhead by avoiding repeated calculations.

This solution defines a helper function calculate(i, j) which returns the best possible score a player can achieve from the subarray nums[i..j]. The player picks either the start or the end of the subarray. The opponent then plays optimally on the remaining subarray.

The recursive formula is max(nums[i] - calculate(i+1, j), nums[j] - calculate(i, j-1)), where the player's score is reduced by the opponent's optimal score. Memoization stores the results of calculate(i, j) calls to avoid recomputation.

Code

PythonJavaC++CJavaScriptC#

Python

Java

C++

C

JavaScript

C#

Complexity

Time Complexity: O(n²) - Each state (i, j) is computed once.
Space Complexity: O(n²) - Intermediate results are stored in the memoization table.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach utilizes dynamic programming to solve the problem iteratively. Instead of recursion, it fills up a DP table where each entry represents the best possible score difference a player can achieve for a subarray defined by its boundaries.

The Python solution involves initializing a 2D array dp where dp[i][j] stores the maximum score difference a player can achieve for nums[i...j]. We fill this table bottom-up, considering all possibilities by iterating over lengths of subarrays and their starting indices.

Code

PythonJavaC++CJavaScriptC#

Python

Java

C++

C

JavaScript

C#

Complexity

Time Complexity: O(n²) - The table is filled once for every distinct range.
Space Complexity: O(n²) - The DP table consumes space proportional to n².

Try this approach in the editor →

Approach 3: Memoization Search

We design a function dfs(i, j), which represents the maximum difference in scores between the current player and the other player from the i-th number to the j-th number. The answer is dfs(0, n - 1) geq 0.

The function dfs(i, j) is calculated as follows:

  • If i > j, it means there are no numbers left, so the current player cannot take any points, and the difference is 0, i.e., dfs(i, j) = 0.
  • Otherwise, the current player has two choices. If they choose the i-th number, the difference in scores between the current player and the other player is nums[i] - dfs(i + 1, j). If they choose the j-th number, the difference in scores between the current player and the other player is nums[j] - dfs(i, j - 1). The current player will choose the option with the larger difference, so dfs(i, j) = max(nums[i] - dfs(i + 1, j), nums[j] - dfs(i, j - 1)).

Finally, we only need to check if dfs(0, n - 1) geq 0.

To avoid repeated calculations, we can use memoization. We use an array f to record all the values of dfs(i, j). When the function is called again, we can directly retrieve the answer from f without recalculating it.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Dynamic Programming

We can also use dynamic programming. Define f[i][j] to represent the maximum score difference the current player can achieve in the range nums[i..j]. The final answer is f[0][n - 1] geq 0.

Initially, f[i][i] = nums[i], because with only one number, the current player can only take that number, and the score difference is nums[i].

Consider f[i][j] where i < j, there are two cases:

  • If the current player takes nums[i], the remaining numbers are nums[i + 1..j], and it is the other player's turn. So, f[i][j] = nums[i] - f[i + 1][j].
  • If the current player takes nums[j], the remaining numbers are nums[i..j - 1], and it is the other player's turn. So, f[i][j] = nums[j] - f[i][j - 1].

Therefore, the state transition equation is f[i][j] = max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]).

Finally, we only need to check if f[0][n - 1] geq 0.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.

Similar problem:

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach with Memoization

Time Complexity: O(n²) - Each state (i, j) is computed once.
Space Complexity: O(n²) - Intermediate results are stored in the memoization table.

Dynamic Programming Approach

Time Complexity: O(n²) - The table is filled once for every distinct range.
Space Complexity: O(n²) - The DP table consumes space proportional to n².

Memoization Search—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Game Simulation (Brute Force)O(2^n)O(n)Conceptual understanding of the game tree and decision process
Recursion with MemoizationO(n^2)O(n^2)Top-down implementation that is easy to write during interviews
Bottom-Up Dynamic ProgrammingO(n^2)O(n^2)Preferred when converting recursion to iterative DP for predictable performance

Video Solution

Predict the Winner || LEETCODE 486 || LEETCODE DYNAMIC PROGRAMMING || GAME THEORY • code Explainer • 19,232 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Predict the Winner easy or hard?
Predict the Winner is rated Medium because the main difficulty lies in recognizing the score-difference trick used in game theory problems. Once the recurrence relation is identified, the solution becomes a standard interval dynamic programming problem with O(n^2) complexity.
How to solve Predict the Winner in O(n)?
Predict the Winner cannot be solved in O(n) time in the general case because decisions depend on all possible subarray ranges. The optimal algorithm evaluates O(n^2) states using dynamic programming. Some implementations reduce space to O(n), but the time complexity remains O(n^2).
What is the best approach for Predict the Winner?
The best approach uses dynamic programming based on score difference between players. Define dp[i][j] as the maximum score advantage the current player can achieve from subarray nums[i..j]. The recurrence dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) ensures both players play optimally. This runs in O(n^2) time and O(n^2) space.
What data structure is used in Predict the Winner?
The primary structure is a 2D dynamic programming table or memoization matrix. Each cell dp[i][j] stores the optimal score difference achievable from the subarray between indices i and j. Recursion with caching or bottom-up DP both rely on this structure.
What is the time complexity of Predict the Winner?
The optimal solution runs in O(n^2) time because every subarray (i, j) is computed once and there are roughly n^2 such states. Each state performs constant work comparing two choices. Space complexity is also O(n^2) for the DP table or memoization cache.
Predict the Winner Python or Java solution approach?
Both Python and Java implementations typically use memoized recursion or a bottom-up DP table. The algorithm computes the maximum score difference between players using dp[i][j] transitions. Time complexity remains O(n^2) with O(n^2) memory regardless of language.
Is Predict the Winner asked at Google, Amazon, or Meta?
Predict the Winner represents a classic interval dynamic programming and game theory pattern. Variants of this problem appear in interviews at companies like Amazon, Google, and Meta, especially when testing recursion-to-DP optimization and optimal play reasoning.

Ready to solve this problem?

Practice Predict the Winner with our built-in code editor and test cases.

Practice on FleetCode
Previous

Can I Win

Next

Count The Number of Winning Sequences