#486 Predict the Winner
the problem
In plain words
Two players share a row of numbers. Taking turns, starting with player 1, each player removes one number from either end of the row and adds it to their own score. Both play as well as possible. Return true if player 1 finishes with a score at least as high as player 2's.
in nums = [1,5,2]
out false
Whatever end player 1 takes, player 2 takes the 5: 3 against 5.
in nums = [1,5,233,7]
out true
Player 1 takes 1; whichever end player 2 takes, 233 is left for player 1.
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 10⁷
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval DP
Keep one number per range: lead[i][j] = how far the player to move can get ahead on nums[i..j]. Taking nums[i] hands the opponent the range i + 1..j, where they get ahead by lead[i + 1][j] — so your lead is nums[i] − lead[i + 1][j]. Take the better end.
solutions
From brute force to optimal
lead(i, j) = max(nums[i] − lead(i + 1, j), nums[j] − lead(i, j − 1)); one number left → itself.
- i == j → nums[i].
- Try both ends; the opponent's best lead comes back with a minus sign.
- Player 1 wins if lead(0, n − 1) ≥ 0.
Two branches per turn: 2²⁰ − 1 ≈ 10⁶ calls for n = 20.
Recursion depth n.
class Solution { public boolean predictTheWinner(int[] nums) { return lead(nums, 0, nums.length - 1) >= 0; // a tie counts as a win for player 1 } /** The best (my score - opponent's score) the player to move can force on nums[i..j]. */ private int lead(int[] nums, int i, int j) { if (i == j) return nums[i]; int takeLeft = nums[i] - lead(nums, i + 1, j); // after my pick, the opponent leads by lead(...) int takeRight = nums[j] - lead(nums, i, j - 1); return Math.max(takeLeft, takeRight); }}Only n(n + 1)/2 ranges exist — cache each lead in an Integer[][] (leads can be 0 or negative).
- null = unknown; check, compute, store.
Each range once, O(1) work.
The memo + O(n) stack.
class Solution { public boolean predictTheWinner(int[] nums) { int n = nums.length; return lead(nums, 0, n - 1, new Integer[n][n]) >= 0; // null = unknown (leads can be 0 or negative) } private int lead(int[] nums, int i, int j, Integer[][] memo) { if (i == j) return nums[i]; if (memo[i][j] != null) return memo[i][j]; int best = Math.max(nums[i] - lead(nums, i + 1, j, memo), nums[j] - lead(nums, i, j - 1, memo)); return memo[i][j] = best; }}Fill lead[i][j] for length 1, 2, …, n so the two shorter ranges each cell reads are ready.
- lead[i][i] = nums[i].
- For len = 2..n, for each i (j = i + len − 1): lead[i][j] = max(nums[i] − lead[i + 1][j], nums[j] − lead[i][j − 1]).
- Return lead[0][n − 1] >= 0.
n(n + 1)/2 ranges, two choices each — 210 ranges for n = 20.
The table (one row is enough if i runs downward).
class Solution { public boolean predictTheWinner(int[] nums) { int n = nums.length; int[][] lead = new int[n][n]; // lead[i][j]: best (mover - other) on nums[i..j] for (int i = 0; i < n; i++) lead[i][i] = nums[i]; // one number left: the mover takes it for (int len = 2; len <= n; len++) { // short ranges first: they are what longer ones read for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; int takeLeft = nums[i] - lead[i + 1][j]; // I take nums[i]; the opponent then leads on i+1..j int takeRight = nums[j] - lead[i][j - 1]; // I take nums[j]; the opponent then leads on i..j-1 lead[i][j] = Math.max(takeLeft, takeRight); } } return lead[0][n - 1] >= 0; // a tie still counts as a win for player 1 }}Fill the lead table
in the room
How to say it in the interview
talk track
- "Both play optimally" → minimax. "I'll store one difference per range, not two scores."
- lead[i][j] = max(nums[i] − lead[i + 1][j], nums[j] − lead[i][j − 1]); the diagonal is nums[i].
- Fill by length; return lead[0][n − 1] >= 0. Bonus: with an even count, player 1 never loses — they can take all even-indexed or all odd-indexed numbers.
traps
- Greedy "take the bigger end" loses: [3,9,1,2] — taking 3 leaves the 9 open for the opponent.
- A tie counts as a win: compare with >= 0, not > 0.
- Filling the table row by row from i = 0: lead[i + 1][j] isn't ready. Fill by length, or with i going down.
what they ask next
Follow-ups
Stone Game (LC 877): even count, odd total?
Player 1 always wins — take all even- or all odd-indexed piles, whichever sum is bigger — so the answer is simply true. The same DP proves it.
One row of memory?
For a fixed i, lead[i][j] reads lead[i + 1][j] (the old row) and lead[i][j − 1] (this row): loop i downward and j upward over one array.
before you submit
Edge cases to test
- One number → true: player 1 takes it.
- A tie → true.
- An even count of numbers → always true (the DP doesn't need this trick).
practise next
Similar problems
- #312Burst BalloonsHardin Dynamic Programming
- #5Longest Palindromic SubstringMediumin Dynamic Programming