Predict the Winner
Predict the Winner is a medium dynamic programming problem solved with the interval dp pattern.
The best approach, optimal (interval dp on the score margin), runs in O(n²) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try both ends recursively) up.
Problem
Two players play a game on an integer array nums. They take turns, and Player 1 moves first. On each turn the current player removes one number from either end of the array and adds it to their own score. The game ends when the array is empty.
Both players play optimally. Return true if Player 1 can finish with a score greater than or equal to Player 2’s score, and false otherwise.
Examples
Example 1
- Input
nums = [2, 9, 3]- Output
false- Why
- Whichever end Player 1 takes, Player 2 grabs the 9 next, so Player 1 ends with at most 5 against 9.
Example 2
- Input
nums = [4, 1, 10, 3]- Output
true- Why
- Player 1 takes 4; Player 2 must take 1 or 3, which uncovers the 10 for Player 1. Player 1 finishes with 14 against 4.
Example 3
- Input
nums = [6]- Output
true- Why
- Player 1 takes the only number and Player 2 scores nothing.
Constraints
1 <= nums.length <= 200 <= nums[i] <= 10^7
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try both ends recursively) | O(2ⁿ) | O(n) |
| Optimal (interval DP on the score margin) | O(n²) | O(n) |
1Brute force (try both ends recursively)
O(2ⁿ)Every call branches into two calls on an interval one shorter, so the recursion tree has about 2ⁿ nodes.O(n)Recursion depth is at most n.Let diff(i, j) be the best score margin the player to move can achieve on nums[i..j]. Taking the left end gives nums[i], after which the opponent achieves diff(i + 1, j) against you, so your margin is nums[i] - diff(i + 1, j); the right end is symmetric. Player 1 wins if diff(0, n - 1) >= 0.
- diff(i, j): if i == j return nums[i].
- Return max(nums[i] - diff(i + 1, j), nums[j] - diff(i, j - 1)).
- Answer: diff(0, n - 1) >= 0.
class Solution {
public boolean predictTheWinner(int[] nums) {
return diff(nums, 0, nums.length - 1) >= 0;
}
private int diff(int[] nums, int i, int j) {
if (i == j) return nums[i];
int takeLeft = nums[i] - diff(nums, i + 1, j);
int takeRight = nums[j] - diff(nums, i, j - 1);
return Math.max(takeLeft, takeRight);
}
}class Solution:
def predictTheWinner(self, nums: List[int]) -> bool:
def diff(i: int, j: int) -> int:
if i == j:
return nums[i]
return max(nums[i] - diff(i + 1, j), nums[j] - diff(i, j - 1))
return diff(0, len(nums) - 1) >= 0class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
return diff(nums, 0, nums.size() - 1) >= 0;
}
private:
int diff(vector<int>& nums, int i, int j) {
if (i == j) return nums[i];
int takeLeft = nums[i] - diff(nums, i + 1, j);
int takeRight = nums[j] - diff(nums, i, j - 1);
return max(takeLeft, takeRight);
}
};function predictTheWinner(nums) {
const diff = (i, j) => {
if (i === j) return nums[i];
return Math.max(nums[i] - diff(i + 1, j), nums[j] - diff(i, j - 1));
};
return diff(0, nums.length - 1) >= 0;
}2Optimal (interval DP on the score margin)
O(n²)Each of the n(n - 1) / 2 intervals is computed once in O(1).O(n)A single row of n margins is reused for every left index.The recursion only ever asks about O(n²) intervals, so compute each once. Process intervals by increasing left index from right to left, and keep one row dp[j] = margin on nums[i..j] for the current i. When dp[j] is updated, dp[j] still holds the value for (i + 1, j) and dp[j - 1] already holds the new value for (i, j - 1).
- dp = copy of nums (intervals of length 1).
- For i from n - 2 down to 0, for j from i + 1 to n - 1: dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]).
- Return dp[n - 1] >= 0.
class Solution {
public boolean predictTheWinner(int[] nums) {
int n = nums.length;
int[] dp = nums.clone();
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
return dp[n - 1] >= 0;
}
}class Solution:
def predictTheWinner(self, nums: List[int]) -> bool:
n = len(nums)
dp = nums[:]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1])
return dp[n - 1] >= 0class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
vector<int> dp(nums);
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
return dp[n - 1] >= 0;
}
};function predictTheWinner(nums) {
const n = nums.length;
const dp = nums.slice();
for (let i = n - 2; i >= 0; i--) {
for (let j = i + 1; j < n; j++) {
dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
return dp[n - 1] >= 0;
}Edge cases to test
- A single number: Player 1 always wins
- A tie counts as a win for Player 1, e.g. [5, 5]
- All zeros
- Greedy (always take the larger end) fails, e.g. [1, 5, 233, 7]
Hints
Hint 1
Taking the larger end is not always best. You need to look ahead at what the opponent can do with the remaining interval.
Hint 2
Instead of tracking two scores, track one number: the current player's score minus the opponent's score on the interval nums[i..j].
Hint 3
diff(i, j) = max(nums[i] - diff(i + 1, j), nums[j] - diff(i, j - 1)). There are only O(n²) intervals, so fill them bottom-up by length.
FAQ
What is the best time complexity for Predict the Winner?
Optimal (interval DP on the score margin) runs in O(n²) time and O(n) extra space. Each of the n(n - 1) / 2 intervals is computed once in O(1).
Which pattern does Predict the Winner use?
It is a dynamic programming problem that uses the interval dp pattern. Other problems with the same pattern: Matrix Chain Multiplication, Burst Balloons, The Score of Students Solving Math Expression.
Is there a brute force solution for Predict the Winner?
Yes. Brute force (try both ends recursively) takes O(2ⁿ) time and O(n) space. Let diff(i, j) be the best score margin the player to move can achieve on nums[i..j].
Which edge cases should I test for Predict the Winner?
A single number: Player 1 always wins; A tie counts as a win for Player 1, e.g. [5, 5]; All zeros; Greedy (always take the larger end) fails, e.g. [1, 5, 233, 7].