Predict the Winner (LeetCode 486)
You will see how scoring every range from the side of the player about to move turns a two-player game into one table.
Decide whether Player 1 can finish a two-player game on the array nums with a total at least as large as Player 2's.
The players alternate, and Player 1 moves first. A move takes the number at the left end or the right end of what is left of the array and adds it to the mover's total; totals start at 0, and the game is over once the array is empty. Assume each player always picks the move that is best for them.
Return true when Player 1 finishes with no less than Player 2 (equal totals also give true), and false otherwise.
Worked Examples
nums = [1,5,2]falsenums = [1,5,233,7]true⚖️Formal Constraints & Bounds
1 <= nums.length <= 200 <= nums[i] <= 107
Why It Works & Core Invariant
Both players follow the same rule, so one number per range, the lead of whoever moves there, describes the whole game: a move is worth the number taken minus the opponent's lead on what remains, and the mover keeps the better of the two ends.
Real-World Scenario & Production Applications
Any turn-based contest with perfect information has this shape: two agents alternate actions on a shared state and each maximizes its own result. Game-playing programs, auction and negotiation models, and adversarial test generators all value a move by what it gains minus the best answer it allows.
Step-by-Step Execution Trace Table
Example 2, nums = [1,5,233,7] (n = 4). Rows are filled from i = 3 down; each cell is the mover's best lead on nums[i..j]:
| Step | (i, j) | take_left = nums[i] - diff[i + 1][j] | take_right = nums[j] - diff[i][j - 1] | diff[i][j] |
|---|---|---|---|---|
| 1 | (3, 3) | one number left | 7 | |
| 2 | (2, 2) | one number left | 233 | |
| 3 | (2, 3) | 233 - 7 = 226 | 7 - 233 = -226 | 226 |
| 4 | (1, 1) | one number left | 5 | |
| 5 | (1, 2) | 5 - 233 = -228 | 233 - 5 = 228 | 228 |
| 6 | (1, 3) | 5 - 226 = -221 | 7 - 228 = -221 | -221 |
| 7 | (0, 0) | one number left | 1 | |
| 8 | (0, 1) | 1 - 5 = -4 | 5 - 1 = 4 | 4 |
| 9 | (0, 2) | 1 - 228 = -227 | 233 - 4 = 229 | 229 |
| 10 | (0, 3) | 1 - (-221) = 222 | 7 - 229 = -222 | 222 |
| End | diff[0][3] >= 0 | true |
At step 10 the bigger end, 7, is the worse move: it leaves [1, 5, 233], where the opponent leads by 229. Taking 1 leaves [5, 233, 7], where the opponent can only fall behind by 221. Player 1 ends ahead by 222 (234 against 12).
| 1 | Score every range from the side of the player about to move: `diff[i][j]` is the most that player can end ahead on `nums[i..j]`. |
| 2 | A move takes one end and hands the rest to the opponent, who then leads by the rest's `diff`: `take_left = nums[i] - diff[i + 1][j]`, `take_right = nums[j] - diff[i][j - 1]`, and `diff[i][j]` keeps the larger. |
| 3 | The shape: an outer loop over the start `i`, an inner loop over the end `j > i`, a one-number base case set before the inner loop, and the answer read from the whole range. |
| 4 | The trap: subtract the reply, never add it, and don't just take the bigger end: on `[1, 5, 233, 7]` taking 7 hands 233 to the opponent; only `nums[0] - diff[1][3]` shows that taking 1 wins. |
Target: Predict the Winner (LeetCode 486). `diff[i][j]` is the most the player about to move on `nums[i..j]` can end ahead. Both players use the same table, because both play the same way.
Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).
Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In a two-player game where both sides play perfectly, "what should I do?" depends on "what will the other player do next?", which depends on what I do after that. Minimax DP cuts that chain by scoring every position from the side of the player about to move. Here the positions are the ranges nums[i..j] still on the table, and diff[i][j] is the most the player to move can end ahead there. A move takes one end and hands the rest to the opponent, who then ends ahead by the rest's own diff. So a move is worth the number taken minus that reply.
♟️ The Analogy: Chess Players Who Think One Reply Ahead
A strong player never judges a move by what it grabs. They ask what the opponent's best answer is, and they value the move as "what I gain minus what that answer gains back". If you already know how good every smaller position is for whoever moves in it, you only need to look one reply ahead: the rest of the game is already inside those numbers.
🪄 The Mathematical Harmony / Magic Trick
for i in range(n - 1, -1, -1): diff[i][i] = nums[i] for j in range(i + 1, n): take_left = nums[i] - diff[i + 1][j] take_right = nums[j] - diff[i][j - 1] diff[i][j] = max(take_left, take_right)return diff[0][n - 1] >= 0 The minus sign is the whole idea: diff[i + 1][j] is the opponent's lead after I take nums[i], so it counts against me. Both players maximize their own lead with the same rule, so one table describes both of them, and every shorter range is final before a longer one reads it.
💡 Summary
Score each range from the mover's side, value a move as what it takes minus the opponent's lead on what remains, keep the better move, and read the whole game at diff[0][n - 1]. time and space.
Adding the reply, or taking the bigger end:
take_left = nums[i] - diff[i + 1][j]. The rest of the range is the opponent's turn, so its value counts against you; adding it, or grabbing the bigger end, loses[1, 5, 233, 7], where the right first move is the smaller end, 1.Treating a tie as a loss: return
diff[0][n - 1] >= 0, not> 0. A tie counts as a win for Player 1 ([2, 4, 2]is a 4-4 tie and returnstrue).Filling rows from the top: run
ifromn - 1down to0.diff[i][j]readsdiff[i + 1][j], a row further down; filling fromi = 0reads it while it is still0.Leaving out the one-number range: set
diff[i][i] = nums[i]before thejloop. Without it a one-number range reads as 0, and every longer range is built on that wrong value.
4-Phase Thought Process Model
You will see how a senior engineer spots a two-player game with perfect play and answers it with one table of leads.
Pattern Recognition Signals
The 10-second spot
"A two-player game", "takes the number at the left end or the right end" and "each player always picks the move that is best for them": the same shared state is played by both sides, and every move is answered by the opponent's best reply. That is the signal for Minimax DP: score each position from the side of the player about to move.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
diff[i][j] is the most the player about to move on nums[i..j] can end ahead of the other, and every shorter range is final before it is read. diff[i][i] = nums[i]; diff[i][j] = max(take_left, take_right) with take_left = nums[i] - diff[i + 1][j] and take_right = nums[j] - diff[i][j - 1]. Player 1 wins when diff[0][n - 1] >= 0.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
take_left = nums[i] - diff[i + 1][j], not+, and not the bigger end: the rest is the opponent's turn, so its lead counts against you. On[1, 5, 233, 7]taking the bigger end, 7, hands 233 to the opponent and loses.return diff[0][n - 1] >= 0, not> 0: a tie counts as a win for Player 1 ([2, 4, 2]is a 4-4 tie and returnstrue).for i in range(n - 1, -1, -1):diff[i][j]readsdiff[i + 1][j], a row further down; filling fromi = 0reads it while it is still0.diff[i][i] = nums[i]before thejloop: without it every one-number range reads as 0, and every longer range is built on that wrong value.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Minimax DP. Both players play perfectly, so I score every range from the side of the player about to move: diff of i, j is the most that player can end ahead on nums from i to j. If they take the left number, the opponent then moves on the rest and ends ahead by diff of i plus one, j, so that move is worth nums of i minus that. Taking the right number works the same way, and the mover keeps the better of the two. I fill the rows from the bottom up, so every shorter range is final before it's read. The trap is adding the rest, or grabbing the bigger end: the rest is the opponent's turn, so it counts against me. Player 1 wins when diff of zero, n minus one is at least zero, since a tie counts as a win. That's O(N squared) time and space.
So: diff[i][j] = the mover's best lead on nums[i..j]; max(nums[i] - diff[i + 1][j], nums[j] - diff[i][j - 1]), filled bottom row up; answer diff[0][n - 1] >= 0.
Complexity & Mathematical Proof
O(N^2)
Look at the code: for i in range(n - 1, -1, -1) runs N times, and for each i the inner for j in range(i + 1, n) runs n - 1 - i times, so the inner body runs N(N - 1)/2 times in all. Each run does two subtractions and one max, which is O(1), and each i also sets diff[i][i] once. Building diff takes N^2 steps once. Total: O(N^2).
O(N^2)
The code keeps the diff table of N x N integers (only the cells with i <= j are used), plus a few integers. The answer is one boolean. Each row only reads the row below it, so two rows would be enough, but the full table keeps the code closest to the idea.
Look at the code: for i in range(n - 1, -1, -1) runs N times, and for each i the inner for j in range(i + 1, n) runs n - 1 - i times, so the inner body runs N(N - 1)/2 times in all. Each run does two subtractions and one max, which is O(1), and each i also sets diff[i][i] once. Building diff takes N^2 steps once. Total: O(N^2).
Derivation Progression
O(N^2)
diff = [[0] * n for _ in range(n)] creates N rows of N zeros once.
N iterations
for i in range(n - 1, -1, -1) visits every start index once, from the last to the first, and sets diff[i][i] = nums[i].
N(N - 1)/2 iterations in all
for j in range(i + 1, n) visits every longer range that starts at i.
O(1)
take_left and take_right are one subtraction each, and diff[i][j] is one max.
O(N^2)
Every range is scored once in constant time; the answer is one comparison, diff[0][n - 1] >= 0.
Variable Definitions
Length of nums, the number of numbers in the game
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N^2): the diff table
O(1): one boolean
Boundary Best / Worst Cases
: every range is filled whatever the numbers are
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"a two-player game on the array nums"**, "takes the number at the left end or the right end", "each player always picks the move that is best for them". One shared state, alternating moves, perfect play: Minimax DP, scoring each range from the side of the player about to move.
numbers up to , so a lead is at most and fits a 32-bit integer. The memo-free game tree has at most lines of play and passes at this size, but it is exponential; the table scores the ranges once each, time and space.
Adding the reply or grabbing the bigger end ignores the opponent's best answer ([1, 5, 233, 7] must return true). A tie is a Player 1 win, so compare with >= 0. In a game engine the same table would be shared by many searches: key it by the position, not by whose turn it is, since the value is always from the mover's side.
Core Algorithmic State Invariants
`diff[i][j]` is the most the player about to move on `nums[i..j]` can end ahead. Both players use the same rule, so one table describes both of them.
`take_left = nums[i] - diff[i + 1][j]` and `take_right = nums[j] - diff[i][j - 1]`: after the move the opponent leads by the shorter range's `diff`, so it is subtracted. Grabbing the bigger end ignores that reply.
Rows are filled from `i = n - 1` down, so every shorter range is final before it is read. N(N + 1)/2 ranges at O(1) each: O(N^2) time and space; Player 1 wins when `diff[0][n - 1] >= 0`.
Predict the Winner (LeetCode 486)
You will see how scoring every range from the side of the player about to move turns a two-player game into one table.
Decide whether Player 1 can finish a two-player game on the array nums with a total at least as large as Player 2's.
The players alternate, and Player 1 moves first. A move takes the number at the left end or the right end of what is left of the array and adds it to the mover's total; totals start at 0, and the game is over once the array is empty. Assume each player always picks the move that is best for them.
Return true when Player 1 finishes with no less than Player 2 (equal totals also give true), and false otherwise.
Worked Examples
nums = [1,5,2]falsenums = [1,5,233,7]true⚖️Formal Constraints & Bounds
1 <= nums.length <= 200 <= nums[i] <= 107
Why It Works & Core Invariant
Both players follow the same rule, so one number per range, the lead of whoever moves there, describes the whole game: a move is worth the number taken minus the opponent's lead on what remains, and the mover keeps the better of the two ends.
Real-World Scenario & Production Applications
Any turn-based contest with perfect information has this shape: two agents alternate actions on a shared state and each maximizes its own result. Game-playing programs, auction and negotiation models, and adversarial test generators all value a move by what it gains minus the best answer it allows.
Step-by-Step Execution Trace Table
Example 2, nums = [1,5,233,7] (n = 4). Rows are filled from i = 3 down; each cell is the mover's best lead on nums[i..j]:
| Step | (i, j) | take_left = nums[i] - diff[i + 1][j] | take_right = nums[j] - diff[i][j - 1] | diff[i][j] |
|---|---|---|---|---|
| 1 | (3, 3) | one number left | 7 | |
| 2 | (2, 2) | one number left | 233 | |
| 3 | (2, 3) | 233 - 7 = 226 | 7 - 233 = -226 | 226 |
| 4 | (1, 1) | one number left | 5 | |
| 5 | (1, 2) | 5 - 233 = -228 | 233 - 5 = 228 | 228 |
| 6 | (1, 3) | 5 - 226 = -221 | 7 - 228 = -221 | -221 |
| 7 | (0, 0) | one number left | 1 | |
| 8 | (0, 1) | 1 - 5 = -4 | 5 - 1 = 4 | 4 |
| 9 | (0, 2) | 1 - 228 = -227 | 233 - 4 = 229 | 229 |
| 10 | (0, 3) | 1 - (-221) = 222 | 7 - 229 = -222 | 222 |
| End | diff[0][3] >= 0 | true |
At step 10 the bigger end, 7, is the worse move: it leaves [1, 5, 233], where the opponent leads by 229. Taking 1 leaves [5, 233, 7], where the opponent can only fall behind by 221. Player 1 ends ahead by 222 (234 against 12).
| 1 | Score every range from the side of the player about to move: `diff[i][j]` is the most that player can end ahead on `nums[i..j]`. |
| 2 | A move takes one end and hands the rest to the opponent, who then leads by the rest's `diff`: `take_left = nums[i] - diff[i + 1][j]`, `take_right = nums[j] - diff[i][j - 1]`, and `diff[i][j]` keeps the larger. |
| 3 | The shape: an outer loop over the start `i`, an inner loop over the end `j > i`, a one-number base case set before the inner loop, and the answer read from the whole range. |
| 4 | The trap: subtract the reply, never add it, and don't just take the bigger end: on `[1, 5, 233, 7]` taking 7 hands 233 to the opponent; only `nums[0] - diff[1][3]` shows that taking 1 wins. |
Target: Predict the Winner (LeetCode 486). `diff[i][j]` is the most the player about to move on `nums[i..j]` can end ahead. Both players use the same table, because both play the same way.
Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).
Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In a two-player game where both sides play perfectly, "what should I do?" depends on "what will the other player do next?", which depends on what I do after that. Minimax DP cuts that chain by scoring every position from the side of the player about to move. Here the positions are the ranges nums[i..j] still on the table, and diff[i][j] is the most the player to move can end ahead there. A move takes one end and hands the rest to the opponent, who then ends ahead by the rest's own diff. So a move is worth the number taken minus that reply.
♟️ The Analogy: Chess Players Who Think One Reply Ahead
A strong player never judges a move by what it grabs. They ask what the opponent's best answer is, and they value the move as "what I gain minus what that answer gains back". If you already know how good every smaller position is for whoever moves in it, you only need to look one reply ahead: the rest of the game is already inside those numbers.
🪄 The Mathematical Harmony / Magic Trick
for i in range(n - 1, -1, -1): diff[i][i] = nums[i] for j in range(i + 1, n): take_left = nums[i] - diff[i + 1][j] take_right = nums[j] - diff[i][j - 1] diff[i][j] = max(take_left, take_right)return diff[0][n - 1] >= 0 The minus sign is the whole idea: diff[i + 1][j] is the opponent's lead after I take nums[i], so it counts against me. Both players maximize their own lead with the same rule, so one table describes both of them, and every shorter range is final before a longer one reads it.
💡 Summary
Score each range from the mover's side, value a move as what it takes minus the opponent's lead on what remains, keep the better move, and read the whole game at diff[0][n - 1]. time and space.
Adding the reply, or taking the bigger end:
take_left = nums[i] - diff[i + 1][j]. The rest of the range is the opponent's turn, so its value counts against you; adding it, or grabbing the bigger end, loses[1, 5, 233, 7], where the right first move is the smaller end, 1.Treating a tie as a loss: return
diff[0][n - 1] >= 0, not> 0. A tie counts as a win for Player 1 ([2, 4, 2]is a 4-4 tie and returnstrue).Filling rows from the top: run
ifromn - 1down to0.diff[i][j]readsdiff[i + 1][j], a row further down; filling fromi = 0reads it while it is still0.Leaving out the one-number range: set
diff[i][i] = nums[i]before thejloop. Without it a one-number range reads as 0, and every longer range is built on that wrong value.
4-Phase Thought Process Model
You will see how a senior engineer spots a two-player game with perfect play and answers it with one table of leads.
Pattern Recognition Signals
The 10-second spot
"A two-player game", "takes the number at the left end or the right end" and "each player always picks the move that is best for them": the same shared state is played by both sides, and every move is answered by the opponent's best reply. That is the signal for Minimax DP: score each position from the side of the player about to move.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
diff[i][j] is the most the player about to move on nums[i..j] can end ahead of the other, and every shorter range is final before it is read. diff[i][i] = nums[i]; diff[i][j] = max(take_left, take_right) with take_left = nums[i] - diff[i + 1][j] and take_right = nums[j] - diff[i][j - 1]. Player 1 wins when diff[0][n - 1] >= 0.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
take_left = nums[i] - diff[i + 1][j], not+, and not the bigger end: the rest is the opponent's turn, so its lead counts against you. On[1, 5, 233, 7]taking the bigger end, 7, hands 233 to the opponent and loses.return diff[0][n - 1] >= 0, not> 0: a tie counts as a win for Player 1 ([2, 4, 2]is a 4-4 tie and returnstrue).for i in range(n - 1, -1, -1):diff[i][j]readsdiff[i + 1][j], a row further down; filling fromi = 0reads it while it is still0.diff[i][i] = nums[i]before thejloop: without it every one-number range reads as 0, and every longer range is built on that wrong value.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Minimax DP. Both players play perfectly, so I score every range from the side of the player about to move: diff of i, j is the most that player can end ahead on nums from i to j. If they take the left number, the opponent then moves on the rest and ends ahead by diff of i plus one, j, so that move is worth nums of i minus that. Taking the right number works the same way, and the mover keeps the better of the two. I fill the rows from the bottom up, so every shorter range is final before it's read. The trap is adding the rest, or grabbing the bigger end: the rest is the opponent's turn, so it counts against me. Player 1 wins when diff of zero, n minus one is at least zero, since a tie counts as a win. That's O(N squared) time and space.
So: diff[i][j] = the mover's best lead on nums[i..j]; max(nums[i] - diff[i + 1][j], nums[j] - diff[i][j - 1]), filled bottom row up; answer diff[0][n - 1] >= 0.
Complexity & Mathematical Proof
O(N^2)
Look at the code: for i in range(n - 1, -1, -1) runs N times, and for each i the inner for j in range(i + 1, n) runs n - 1 - i times, so the inner body runs N(N - 1)/2 times in all. Each run does two subtractions and one max, which is O(1), and each i also sets diff[i][i] once. Building diff takes N^2 steps once. Total: O(N^2).
O(N^2)
The code keeps the diff table of N x N integers (only the cells with i <= j are used), plus a few integers. The answer is one boolean. Each row only reads the row below it, so two rows would be enough, but the full table keeps the code closest to the idea.
Look at the code: for i in range(n - 1, -1, -1) runs N times, and for each i the inner for j in range(i + 1, n) runs n - 1 - i times, so the inner body runs N(N - 1)/2 times in all. Each run does two subtractions and one max, which is O(1), and each i also sets diff[i][i] once. Building diff takes N^2 steps once. Total: O(N^2).
Derivation Progression
O(N^2)
diff = [[0] * n for _ in range(n)] creates N rows of N zeros once.
N iterations
for i in range(n - 1, -1, -1) visits every start index once, from the last to the first, and sets diff[i][i] = nums[i].
N(N - 1)/2 iterations in all
for j in range(i + 1, n) visits every longer range that starts at i.
O(1)
take_left and take_right are one subtraction each, and diff[i][j] is one max.
O(N^2)
Every range is scored once in constant time; the answer is one comparison, diff[0][n - 1] >= 0.
Variable Definitions
Length of nums, the number of numbers in the game
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N^2): the diff table
O(1): one boolean
Boundary Best / Worst Cases
: every range is filled whatever the numbers are
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"a two-player game on the array nums"**, "takes the number at the left end or the right end", "each player always picks the move that is best for them". One shared state, alternating moves, perfect play: Minimax DP, scoring each range from the side of the player about to move.
numbers up to , so a lead is at most and fits a 32-bit integer. The memo-free game tree has at most lines of play and passes at this size, but it is exponential; the table scores the ranges once each, time and space.
Adding the reply or grabbing the bigger end ignores the opponent's best answer ([1, 5, 233, 7] must return true). A tie is a Player 1 win, so compare with >= 0. In a game engine the same table would be shared by many searches: key it by the position, not by whose turn it is, since the value is always from the mover's side.
Core Algorithmic State Invariants
`diff[i][j]` is the most the player about to move on `nums[i..j]` can end ahead. Both players use the same rule, so one table describes both of them.
`take_left = nums[i] - diff[i + 1][j]` and `take_right = nums[j] - diff[i][j - 1]`: after the move the opponent leads by the shorter range's `diff`, so it is subtracted. Grabbing the bigger end ignores that reply.
Rows are filled from `i = n - 1` down, so every shorter range is final before it is read. N(N + 1)/2 ranges at O(1) each: O(N^2) time and space; Player 1 wins when `diff[0][n - 1] >= 0`.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Score every range from the side of the player to move | diff = [[0] * n for _ in range(n)] | `diff[i][j]` is the most the player about to move on `nums[i..j]` can end ahead. Both players use the same table, because both play the same way. |
| Short ranges first | for i in range(n - 1, -1, -1): | `diff[i][j]` reads `diff[i + 1][j]`, a row further down, so the rows are filled from the bottom up. |
| One number left | diff[i][i] = nums[i] | The mover takes it and ends ahead by exactly that number. |
| Each move minus the opponent's best reply (the trap) | take_left = nums[i] - diff[i + 1][j]
take_right = nums[j] - diff[i][j - 1] | After a move it is the opponent's turn on the shorter range, and the opponent ends ahead by that range's `diff`. So the reply is subtracted, never added, and the bigger end is not always the better move. |
| The mover keeps the better move | diff[i][j] = max(take_left, take_right) | Playing optimally means maximizing your own lead; the opponent's best play is already inside the two `diff` values. |
| Answer from Player 1's side | return diff[0][n - 1] >= 0 | Player 1 moves first on the whole array; a lead of 0 is a tie, which counts as a win. |