Predict the Winner solution and explanation
Cisco
Google
9 more videos on this problem
Predict the Winner || LEETCODE 486 || LEETCODE DYNAMIC PROGRAMMING || GAME THEORYcode Explainer · 12:13 · 19K views
Predict the Winner | Two Recursive Approaches | Memoization | Game Strategy | AMAZON | Leetcode-486codestorywithMIK · 27:35 · 18K views
Leetcode 486 Predict the WinnerJeevan Kumar - Cracckify · 10:29 · 9K views
486. Predict the Winner (Leetcode Medium)Programming Live with Larry · 7:55 · 6K views
486. Predict the Winner | Day 004 | Game Theory | Recursion | Top-Down | Bottom Up Optimised DPAryan Mittal · 23:40 · 4K views
Predict the Winner - LeetCode 486 - Python - DPAlpha-Code · 15:42 · 2K views
Leetcode 486. Predict the WinnerElite Code · 15:59 · 1K views
Leetcode 486 (Medium) Predict the Winnertinman · 21:42 · 1K views
Crack the LeetCode 486. Predict the Winner with Dynamic Programming! 💻🏆 | Multi-language SolutionsvanAmsen · 8:23 · 1K views
Daily Leetcode #1214: Jul 28, 2023 - 486. Predict the WinnerProgramming Live with Larry · 14:03 · 1K views
The problem
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 <= 200 <= 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.
def PredictTheWinner(nums):
def calculate(i, j):
if i == j:
return nums[i]
if memo[i][j] != -1:
return memo[i][j]
pick_i = nums[i] - calculate(i + 1, j)
pick_j = nums[j] - calculate(i, j - 1)
memo[i][j] = max(pick_i, pick_j)
return memo[i][j]
length = len(nums)
memo = [[-1 for _ in range(length)] for _ in range(length)]
return calculate(0, length - 1) >= 0public class Solution {
public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
int[][] memo = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = Integer.MIN_VALUE;
}
}
return calculate(nums, 0, n - 1, memo) >= 0;
}
private int calculate(int[] nums, int i, int j, int[][] memo) {
if (i == j) return nums[i];
if (memo[i][j] != Integer.MIN_VALUE) return memo[i][j];
int pickI = nums[i] - calculate(nums, i + 1, j, memo);
int pickJ = nums[j] - calculate(nums, i, j - 1, memo);
memo[i][j] = Math.max(pickI, pickJ);
return memo[i][j];
}
}#include <vector>
#include <algorithm>
class Solution {
public:
bool PredictTheWinner(std::vector<int>& nums) {
int n = nums.size();
std::vector<std::vector<int>> memo(n, std::vector<int>(n, INT_MIN));
return calculate(nums, 0, n - 1, memo) >= 0;
}
private:
int calculate(std::vector<int>& nums, int i, int j, std::vector<std::vector<int>>& memo) {
if (i == j) return nums[i];
if (memo[i][j] != INT_MIN) return memo[i][j];
int pickI = nums[i] - calculate(nums, i + 1, j, memo);
int pickJ = nums[j] - calculate(nums, i, j - 1, memo);
memo[i][j] = std::max(pickI, pickJ);
return memo[i][j];
}
};function PredictTheWinner(nums) {
const length = nums.length;
const memo = Array.from({ length }, () => Array(length).fill(null));
const calculate = (i, j) => {
if (i === j) return nums[i];
if (memo[i][j] !== null) return memo[i][j];
const pickI = nums[i] - calculate(i + 1, j);
const pickJ = nums[j] - calculate(i, j - 1);
memo[i][j] = Math.max(pickI, pickJ);
return memo[i][j];
};
return calculate(0, length - 1) >= 0;
}#include <stdio.h>
#include <limits.h>
int calculate(int* nums, int i, int j, int** memo) {
if (i == j) return nums[i];
if (memo[i][j] != INT_MIN) return memo[i][j];
int pickI = nums[i] - calculate(nums, i + 1, j, memo);
int pickJ = nums[j] - calculate(nums, i, j - 1, memo);
memo[i][j] = (pickI > pickJ) ? pickI : pickJ;
return memo[i][j];
}
int PredictTheWinner(int* nums, int numsSize) {
int** memo = (int**) malloc(numsSize * sizeof(int*));
for (int i = 0; i < numsSize; ++i) {
memo[i] = (int*) malloc(numsSize * sizeof(int));
for (int j = 0; j < numsSize; ++j) memo[i][j] = INT_MIN;
}
int result = calculate(nums, 0, numsSize - 1, memo) >= 0;
for (int i = 0; i < numsSize; ++i) free(memo[i]);
free(memo);
return result;
}public class Solution {
public bool PredictTheWinner(int[] nums) {
int n = nums.Length;
int[,] memo = new int[n, n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
memo[i, j] = int.MinValue;
return Calculate(nums, 0, n - 1, memo) >= 0;
}
private int Calculate(int[] nums, int start, int end, int[,] memo) {
if (start == end) return nums[start];
if (memo[start, end] != int.MinValue) return memo[start, end];
int pickStart = nums[start] - Calculate(nums, start + 1, end, memo);
int pickEnd = nums[end] - Calculate(nums, start, end - 1, memo);
memo[start, end] = Math.Max(pickStart, pickEnd);
return memo[start, end];
}
}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.
Time Complexity: O(n²) - Each state (i, j) is computed once.
Space Complexity: O(n²) - Intermediate results are stored in the memoization table.
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.
def PredictTheWinner(nums):
n = len(nums)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = nums[i]
for len in range(2, n + 1):
for i in range(n - len + 1):
j = i + len - 1
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
return dp[0][n - 1] >= 0public class Solution {
public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
int[][] dp = new int[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 <= n - len; 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;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
bool PredictTheWinner(std::vector<int>& nums) {
int n = nums.size();
std::vector<std::vector<int>> dp(n, std::vector<int>(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 <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = std::max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
};function PredictTheWinner(nums) {
const n = nums.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
dp[i][i] = nums[i];
}
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const 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;
}#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
bool PredictTheWinner(int* nums, int numsSize) {
int** dp = (int**) malloc(numsSize * sizeof(int*));
for (int i = 0; i < numsSize; ++i) {
dp[i] = (int*) malloc(numsSize * sizeof(int));
for (int j = 0; j < numsSize; ++j) dp[i][j] = 0;
dp[i][i] = nums[i];
}
for (int len = 2; len <= numsSize; ++len) {
for (int i = 0; i <= numsSize - len; ++i) {
int j = i + len - 1;
dp[i][j] = (nums[i] - dp[i + 1][j] > nums[j] - dp[i][j - 1]) ? nums[i] - dp[i + 1][j] : nums[j] - dp[i][j - 1];
}
}
int result = dp[0][numsSize - 1] >= 0;
for (int i = 0; i < numsSize; ++i) free(dp[i]);
free(dp);
return result;
}public class Solution {
public bool PredictTheWinner(int[] nums) {
int n = nums.Length;
int[,] dp = new int[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 <= n - len; 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;
}
}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.
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².
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 is0, 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 isnums[i] - dfs(i + 1, j). If they choose thej-th number, the difference in scores between the current player and the other player isnums[j] - dfs(i, j - 1). The current player will choose the option with the larger difference, sodfs(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.
function predictTheWinner(nums: number[]): boolean {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
const dfs = (i: number, j: number): number => {
if (i > j) {
return 0;
}
if (f[i][j] === 0) {
f[i][j] = Math.max(nums[i] - dfs(i + 1, j), nums[j] - dfs(i, j - 1));
}
return f[i][j];
};
return dfs(0, n - 1) >= 0;
}func predictTheWinner(nums []int) bool {
n := len(nums)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i > j {
return 0
}
if f[i][j] == 0 {
f[i][j] = max(nums[i]-dfs(i+1, j), nums[j]-dfs(i, j-1))
}
return f[i][j]
}
return dfs(0, n-1) >= 0
}impl Solution {
pub fn predict_the_winner(nums: Vec<i32>) -> bool {
let n = nums.len();
let mut f = vec![vec![0; n]; n];
Self::dfs(&nums, &mut f, 0, n - 1) >= 0
}
fn dfs(nums: &Vec<i32>, f: &mut Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
if i == j {
return nums[i] as i32;
}
if f[i][j] != 0 {
return f[i][j];
}
f[i][j] = std::cmp::max(
nums[i] - Self::dfs(nums, f, i + 1, j),
nums[j] - Self::dfs(nums, f, i, j - 1)
);
f[i][j]
}
}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 arenums[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 arenums[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:
function predictTheWinner(nums: number[]): boolean {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; ++i) {
f[i][i] = nums[i];
}
for (let i = n - 2; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
f[i][j] = Math.max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);
}
}
return f[0][n - 1] >= 0;
}func predictTheWinner(nums []int) bool {
n := len(nums)
f := make([][]int, n)
for i, x := range nums {
f[i] = make([]int, n)
f[i][i] = x
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = max(nums[i]-f[i+1][j], nums[j]-f[i][j-1])
}
}
return f[0][n-1] >= 0
}impl Solution {
pub fn predict_the_winner(nums: Vec<i32>) -> bool {
let n = nums.len();
let mut f = vec![vec![0; n]; n];
for i in 0..n {
f[i][i] = nums[i];
}
for i in (0..n - 1).rev() {
for j in i + 1..n {
f[i][j] = std::cmp::max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);
}
}
f[0][n - 1] >= 0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(n²) - Each state |
| Dynamic Programming Approach | Time Complexity: O(n²) - The table is filled once for every distinct range. |
| Memoization Search | – |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Game Simulation (Brute Force) | O(2^n) | O(n) | Conceptual understanding of the game tree and decision process |
| Recursion with Memoization | O(n^2) | O(n^2) | Top-down implementation that is easy to write during interviews |
| Bottom-Up Dynamic Programming | O(n^2) | O(n^2) | Preferred when converting recursion to iterative DP for predictable performance |
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.