What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P3MediumBuilt on Interval DP~3 min speedrun

Game Theory / Minimax DP (Stone Game, Predict the Winner)

Built on

Interval DPTwo players take turns on one range of items, and each cell keeps the score difference for the player to move.

The problem

Predict the Winner (LC 486)(opens leetcode.com)

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.

Example 1

Input:nums = [1,5,2]

Output:false

Player 2 always gets the 5: once Player 1 takes 1 or 2, the 5 sits at an end. Player 1 ends with 3 against 5.

Minimax DP

shared game state ➔ my gain minus the opponent's best reply ➔ score difference

Spot it when: Two players take turns on the same shared state (numbers at the ends of a row, a pile of stones, a set of moves), both play perfectly, and you must say who wins or by how much: every move is answered by the opponent's best reply.

Minimax DP

Python

1	def predict_the_winner(nums: list[int]) -> bool:
2	"""Predict the Winner: minimax DP on the lead of whoever moves next on nums[i..j].
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(nums)
6	# diff: diff[i][j] is the most the player to move next can end ahead on nums[i..j]
7	diff = [[0] * n for _ in range(n)]
8
9	for i in range(n - 1, -1, -1):
10	# 1. Fill Bottom Row Up:
11	# diff[i + 1][j] must be final before diff[i][j] reads it, so i counts down from n - 1.
12	diff[i][i] = nums[i]
13	for j in range(i + 1, n):
14	# 2. Weigh Each Move Against The Opponent's Best Reply:
15	# Taking nums[i] hands nums[i + 1..j] to the opponent, who then leads by diff[i + 1][j];
16	# that lead counts against the mover, so it is subtracted, not added. take_right mirrors it.
17	take_left = nums[i] - diff[i + 1][j]
18	take_right = nums[j] - diff[i][j - 1]
19	diff[i][j] = max(take_left, take_right)
20
21	# A tie counts as a win for Player 1, so a non-negative final lead is a win.
22	return diff[0][n - 1] >= 0

Invariant: 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.

Score each position from the side of the player about to move: let diff[i][j] be the most that player can end ahead on nums[i..j]. Taking nums[i] hands the opponent nums[i + 1..j], where the opponent now moves and ends ahead by diff[i + 1][j], so the move is worth take_left = nums[i] - diff[i + 1][j]; take_right = nums[j] - diff[i][j - 1] in the same way, and the mover keeps the larger. This is correct because both players follow the same rule, maximizing their own lead, so one table describes both of them and the opponent's best reply is already inside diff[i + 1][j]; filling rows from i = n - 1 down makes every shorter range final before it is read. The whole game is diff[0][n - 1], and Player 1 wins when it is >= 0. The trap is to value a move by what it grabs: adding the rest instead of subtracting the reply, or taking the bigger end. On [1, 5, 233, 7] taking 7 hands 233 to the opponent, and only nums[0] - diff[1][3] shows that taking 1 wins.

See it run

Minimax DP on [1, 5, 2], step by step

i 2

Rows are i and columns are j, written as index:nums[index].

write the range being written
diff[i+1][j] the range left after taking the left end
diff[i][j-1] the range left after taking the right end
answer the final result

diff[i][j] is the most the player to move can end ahead on nums[i..j]. The table for nums = [1, 5, 2] is empty.

0:1

1:5

2:2

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Adding the opponent's lead instead of subtracting it
Mistake
```
take_left = nums[i] + diff[i + 1][j]
take_right = nums[j] + diff[i][j - 1]
```
Fix
```
take_left = nums[i] - diff[i + 1][j]
take_right = nums[j] - diff[i][j - 1]
```
What happens: After you take nums[i], the opponent moves on nums[i + 1..j]. diff[i + 1][j] is the opponent's lead there, so it counts against you. Adding it makes every lead positive. So Player 1 always seems to win.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 2: Taking the bigger end on every move
Mistake
```
scores[turn] += max(nums[lo], nums[hi])
```
Fix
```
diff[i][j] = max(take_left, take_right)
```
What happens: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], taking 7 lets the opponent take 233. Taking 1 wins, and only nums[0] - diff[1][3] shows it.
Example: nums = [1, 5, 233, 7]
Mistake: returns FalseFix: returns True
Gotcha 3: Returning diff[0][n - 1] > 0 instead of >= 0
Mistake
```
return diff[0][n - 1] > 0
```
Fix
```
return diff[0][n - 1] >= 0
```
What happens: The problem counts a tie as a win for Player 1. A tie gives diff[0][n - 1] == 0. > 0 returns False for it.
Example: nums = [2, 4, 2] (a 4-4 tie)
Mistake: returns FalseFix: returns True
Gotcha 4: Filling i upward from 0
Mistake
```
for i in range(n):
```
Fix
```
for i in range(n - 1, -1, -1):
```
What happens: diff[i][j] reads diff[i + 1][j], a row further down. Filling from i = 0 reads that row while it still holds 0. So each move is valued as if the opponent gained nothing.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 5: Leaving out diff[i][i] = nums[i]
Mistake
```
for j in range(i + 1, n):
```
Fix
```
diff[i][i] = nums[i]
for j in range(i + 1, n):
```
What happens: A range with one number has no reply to subtract. The mover takes it, so diff[i][i] = nums[i]. Without that line, every one-number range reads as 0. Every longer range is built on those wrong values.
Example: nums = [1, 3, 2]
Mistake: returns FalseFix: returns True

Not this one if…

Only one player acts and every item in the range must be handled, as in Burst Balloons (LC 312): you choose a split point for your own best total, and there is no opponent's reply to subtract. See Burst Balloons

Deep Dive

Why one table describes both players

This card uses the same range table as Interval DP: one cell for each range nums[i..j], filled from shorter ranges to longer ranges. That part is not repeated here. This card adds two things. The cell holds a score difference, and each range has one player to move.

In a two-player game, a position can be valued from the side of the player who moves next. diff[i][j] is the most that player can end ahead of the other player on nums[i..j].

Both players follow the same rule: each wants the largest lead for themselves. So the same table gives the value for Player 1 and for Player 2. After a move, the roles swap, and the table is read again for the new mover.

This replaces two tables (one score for each player) with one number per range. The number is a difference, so it already contains the opponent's score.

Why the opponent's lead is subtracted

Suppose the mover takes nums[i]. The range nums[i + 1..j] remains, and now the opponent is the player to move. The opponent can end ahead by diff[i + 1][j] on it.

The mover gained nums[i] and the opponent will gain diff[i + 1][j] more than the mover on the rest. So the final lead of the mover for this choice is nums[i] - diff[i + 1][j]. This is take_left. The choice of the right end is take_right = nums[j] - diff[i][j - 1].

The opponent's best reply is already inside diff[i + 1][j], because that value assumes the opponent plays the best move. The mover then keeps the larger of the two choices: diff[i][j] = max(take_left, take_right).

The fill order and a worked table

The range order is the same as in Interval DP. Here the two cells that are read are diff[i + 1][j] and diff[i][j - 1], which are the ranges left after each possible move.

Example: nums = [1, 5, 2]. The diagonal is [1, 5, 2]. diff[0][1] = max(1 - 5, 5 - 1) = 4. diff[1][2] = max(5 - 2, 2 - 5) = 3. diff[0][2] = max(1 - 3, 2 - 4) = -2. The value is negative, so Player 1 loses by 2 and the answer is False.

A tie counts as a win for Player 1 in Predict the Winner (LC 486), so the test is diff[0][n - 1] >= 0.

The cost, and a special case

A state is a range (i, j) with i <= j, so there are about N^2 / 2 states. Each does two subtractions and one max, which is constant work. The time is O(N^2) and the table takes O(N^2) space.

The table can be reduced to one row of O(N) space, because row i reads only row i + 1 and the same row.

In Stone Game (LC 877), the number of piles is even. Then the first player can take all piles at even positions or all piles at odd positions, whichever sum is larger. So the first player never loses, and a table is not required there. For Predict the Winner (LC 486) the length can be odd, so the table is needed.

60-Second Pitch

"Both players play the best move, so I value each range from the view of the player who moves next. diff[i][j] is the most that player can end ahead on nums[i..j]. If the mover takes nums[i], the opponent moves on nums[i + 1..j] and leads by diff[i + 1][j]. So the mover's result is nums[i] - diff[i + 1][j]. The right end works in the same way, and the mover keeps the larger. I fill the table from i = n - 1 down, so shorter ranges are final first. Player 1 wins when diff[0][n - 1] is at least 0. There are about N^2 / 2 ranges with constant work each. That gives O(N^2) time and O(N^2) space, and one row is enough if memory matters."

Common Questions

Why does a greedy choice of the bigger end fail?: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], greedy takes 7 and the opponent then takes 233. The best first move is 1. The opponent then faces [5, 233, 7] and takes 5 or 7, so Player 1 takes 233. The final lead of Player 1 is 222. The table finds this because it includes the opponent's best reply.
Why is the same recurrence used for both players?: The table stores a difference from the view of the player to move. Both players want the largest difference for themselves, so the rule is the same. After a move, the roles swap, and the next value is subtracted. This is why diff[i + 1][j] has a minus sign.
What is the complexity, and can the space be reduced?: The time is O(N^2) because there are about N^2 / 2 ranges with constant work each. The table takes O(N^2) space. Row i reads only row i + 1 and its own earlier columns, so one array of size N is enough for O(N) space.
How does this change for Stone Game (LC 877) or Stone Game II (LC 1140)?: Stone Game (LC 877) has an even number of piles, so the first player always wins, and the table only confirms it. Stone Game II (LC 1140) adds a rule that a move may take up to 2 * m piles, where m is a parameter. The state becomes (i, m), and the same idea applies: the mover's total is the remaining sum minus the opponent's best result.
How do you handle a game where the players do not both maximize a score?: If the game has only win or loss, store a boolean: a position is winning when at least one move leads to a losing position for the opponent. If the score is shared but opposed, the difference form in this card is correct. If the players have different goals, a single table does not apply, and you need one value for each player.

SWE Reasoning

Spot it

Two players take turns on the same shared state, such as a row of numbers or a pile of stones.
Both players play perfectly. The question asks who wins, or by how much.
The values on a move can be added to a score, so the result can be written as a difference of scores.
A move leaves a smaller game of the same kind, such as a shorter range. This gives states (i, j).
A greedy rule, such as taking the bigger end, is tempting. A short counter-example usually shows that it fails.

The invariant, step by step

diff is an n by n table. Row i is processed from i = n - 1 down to 0.
For a range of one number, diff[i][i] = nums[i]: the mover takes it, and the opponent gets nothing.
For j > i, the mover can take nums[i] or nums[j].
After taking nums[i], the opponent moves on nums[i + 1..j] and leads by diff[i + 1][j]. This range is shorter, so it was filled earlier and is final.
The result of this choice for the mover is take_left = nums[i] - diff[i + 1][j]. The other choice is take_right = nums[j] - diff[i][j - 1].
The mover plays the better choice, so diff[i][j] = max(take_left, take_right).
The whole game is diff[0][n - 1]. Player 1 wins when it is at least 0.

Traps

Two tables that are not linked. Keeping a score for each player and maximizing only Player 1's score ignores that Player 2 also plays the best move. Use one table of differences.
Using the even-length shortcut on an odd length. For an even number of piles, the first player never loses, as in Stone Game (LC 877). Predict the Winner (LC 486) allows any length. For nums = [1, 5, 2], the shortcut returns True, but the correct answer is False.
Recursion without a stored table. The plain recursion on (i, j) repeats ranges. For 20 numbers it makes 2,097,151 calls, while the table has only 210 ranges. Store each range once.

Practice

Canonical LeetCode:Predict the Winner (LC 486)Stone Game VII (LC 1690)Stone Game III (LC 1406)Stone Game II (LC 1140)

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P3MediumBuilt on Interval DP~3 min speedrun

Game Theory / Minimax DP (Stone Game, Predict the Winner)

Built on

Interval DPTwo players take turns on one range of items, and each cell keeps the score difference for the player to move.

The problem

Predict the Winner (LC 486)(opens leetcode.com)

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.

Return true when Player 1 finishes with no less than Player 2 (equal totals also give true), and false otherwise.

Example 1

Input:nums = [1,5,2]

Output:false

Player 2 always gets the 5: once Player 1 takes 1 or 2, the 5 sits at an end. Player 1 ends with 3 against 5.

Minimax DP

shared game state ➔ my gain minus the opponent's best reply ➔ score difference

Minimax DP

Python

1	def predict_the_winner(nums: list[int]) -> bool:
2	"""Predict the Winner: minimax DP on the lead of whoever moves next on nums[i..j].
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(nums)
6	# diff: diff[i][j] is the most the player to move next can end ahead on nums[i..j]
7	diff = [[0] * n for _ in range(n)]
8
9	for i in range(n - 1, -1, -1):
10	# 1. Fill Bottom Row Up:
11	# diff[i + 1][j] must be final before diff[i][j] reads it, so i counts down from n - 1.
12	diff[i][i] = nums[i]
13	for j in range(i + 1, n):
14	# 2. Weigh Each Move Against The Opponent's Best Reply:
15	# Taking nums[i] hands nums[i + 1..j] to the opponent, who then leads by diff[i + 1][j];
16	# that lead counts against the mover, so it is subtracted, not added. take_right mirrors it.
17	take_left = nums[i] - diff[i + 1][j]
18	take_right = nums[j] - diff[i][j - 1]
19	diff[i][j] = max(take_left, take_right)
20
21	# A tie counts as a win for Player 1, so a non-negative final lead is a win.
22	return diff[0][n - 1] >= 0

Invariant: 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.

See it run

Minimax DP on [1, 5, 2], step by step

i 2

Rows are i and columns are j, written as index:nums[index].

write the range being written
diff[i+1][j] the range left after taking the left end
diff[i][j-1] the range left after taking the right end
answer the final result

diff[i][j] is the most the player to move can end ahead on nums[i..j]. The table for nums = [1, 5, 2] is empty.

0:1

1:5

2:2

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Adding the opponent's lead instead of subtracting it
Mistake
```
take_left = nums[i] + diff[i + 1][j]
take_right = nums[j] + diff[i][j - 1]
```
Fix
```
take_left = nums[i] - diff[i + 1][j]
take_right = nums[j] - diff[i][j - 1]
```
What happens: After you take nums[i], the opponent moves on nums[i + 1..j]. diff[i + 1][j] is the opponent's lead there, so it counts against you. Adding it makes every lead positive. So Player 1 always seems to win.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 2: Taking the bigger end on every move
Mistake
```
scores[turn] += max(nums[lo], nums[hi])
```
Fix
```
diff[i][j] = max(take_left, take_right)
```
What happens: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], taking 7 lets the opponent take 233. Taking 1 wins, and only nums[0] - diff[1][3] shows it.
Example: nums = [1, 5, 233, 7]
Mistake: returns FalseFix: returns True
Gotcha 3: Returning diff[0][n - 1] > 0 instead of >= 0
Mistake
```
return diff[0][n - 1] > 0
```
Fix
```
return diff[0][n - 1] >= 0
```
What happens: The problem counts a tie as a win for Player 1. A tie gives diff[0][n - 1] == 0. > 0 returns False for it.
Example: nums = [2, 4, 2] (a 4-4 tie)
Mistake: returns FalseFix: returns True
Gotcha 4: Filling i upward from 0
Mistake
```
for i in range(n):
```
Fix
```
for i in range(n - 1, -1, -1):
```
What happens: diff[i][j] reads diff[i + 1][j], a row further down. Filling from i = 0 reads that row while it still holds 0. So each move is valued as if the opponent gained nothing.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 5: Leaving out diff[i][i] = nums[i]
Mistake
```
for j in range(i + 1, n):
```
Fix
```
diff[i][i] = nums[i]
for j in range(i + 1, n):
```
What happens: A range with one number has no reply to subtract. The mover takes it, so diff[i][i] = nums[i]. Without that line, every one-number range reads as 0. Every longer range is built on those wrong values.
Example: nums = [1, 3, 2]
Mistake: returns FalseFix: returns True

Not this one if…

Only one player acts and every item in the range must be handled, as in Burst Balloons (LC 312): you choose a split point for your own best total, and there is no opponent's reply to subtract. See Burst Balloons

Deep Dive

Why one table describes both players

In a two-player game, a position can be valued from the side of the player who moves next. diff[i][j] is the most that player can end ahead of the other player on nums[i..j].

This replaces two tables (one score for each player) with one number per range. The number is a difference, so it already contains the opponent's score.

Why the opponent's lead is subtracted

Suppose the mover takes nums[i]. The range nums[i + 1..j] remains, and now the opponent is the player to move. The opponent can end ahead by diff[i + 1][j] on it.

The fill order and a worked table

The range order is the same as in Interval DP. Here the two cells that are read are diff[i + 1][j] and diff[i][j - 1], which are the ranges left after each possible move.

A tie counts as a win for Player 1 in Predict the Winner (LC 486), so the test is diff[0][n - 1] >= 0.

The cost, and a special case

A state is a range (i, j) with i <= j, so there are about N^2 / 2 states. Each does two subtractions and one max, which is constant work. The time is O(N^2) and the table takes O(N^2) space.

The table can be reduced to one row of O(N) space, because row i reads only row i + 1 and the same row.

60-Second Pitch

Common Questions

Why does a greedy choice of the bigger end fail?: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], greedy takes 7 and the opponent then takes 233. The best first move is 1. The opponent then faces [5, 233, 7] and takes 5 or 7, so Player 1 takes 233. The final lead of Player 1 is 222. The table finds this because it includes the opponent's best reply.
Why is the same recurrence used for both players?: The table stores a difference from the view of the player to move. Both players want the largest difference for themselves, so the rule is the same. After a move, the roles swap, and the next value is subtracted. This is why diff[i + 1][j] has a minus sign.
What is the complexity, and can the space be reduced?: The time is O(N^2) because there are about N^2 / 2 ranges with constant work each. The table takes O(N^2) space. Row i reads only row i + 1 and its own earlier columns, so one array of size N is enough for O(N) space.
How does this change for Stone Game (LC 877) or Stone Game II (LC 1140)?: Stone Game (LC 877) has an even number of piles, so the first player always wins, and the table only confirms it. Stone Game II (LC 1140) adds a rule that a move may take up to 2 * m piles, where m is a parameter. The state becomes (i, m), and the same idea applies: the mover's total is the remaining sum minus the opponent's best result.
How do you handle a game where the players do not both maximize a score?: If the game has only win or loss, store a boolean: a position is winning when at least one move leads to a losing position for the opponent. If the score is shared but opposed, the difference form in this card is correct. If the players have different goals, a single table does not apply, and you need one value for each player.

SWE Reasoning

Spot it

Two players take turns on the same shared state, such as a row of numbers or a pile of stones.
Both players play perfectly. The question asks who wins, or by how much.
The values on a move can be added to a score, so the result can be written as a difference of scores.
A move leaves a smaller game of the same kind, such as a shorter range. This gives states (i, j).
A greedy rule, such as taking the bigger end, is tempting. A short counter-example usually shows that it fails.

The invariant, step by step

diff is an n by n table. Row i is processed from i = n - 1 down to 0.
For a range of one number, diff[i][i] = nums[i]: the mover takes it, and the opponent gets nothing.
For j > i, the mover can take nums[i] or nums[j].
After taking nums[i], the opponent moves on nums[i + 1..j] and leads by diff[i + 1][j]. This range is shorter, so it was filled earlier and is final.
The result of this choice for the mover is take_left = nums[i] - diff[i + 1][j]. The other choice is take_right = nums[j] - diff[i][j - 1].
The mover plays the better choice, so diff[i][j] = max(take_left, take_right).
The whole game is diff[0][n - 1]. Player 1 wins when it is at least 0.

Traps

Two tables that are not linked. Keeping a score for each player and maximizing only Player 1's score ignores that Player 2 also plays the best move. Use one table of differences.
Using the even-length shortcut on an odd length. For an even number of piles, the first player never loses, as in Stone Game (LC 877). Predict the Winner (LC 486) allows any length. For nums = [1, 5, 2], the shortcut returns True, but the correct answer is False.
Recursion without a stored table. The plain recursion on (i, j) repeats ranges. For 20 numbers it makes 2,097,151 calls, while the table has only 210 ranges. Store each range once.

Practice

Canonical LeetCode:Predict the Winner (LC 486)Stone Game VII (LC 1690)Stone Game III (LC 1406)Stone Game II (LC 1140)

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P3MediumBuilt on Interval DP~3 min speedrun

Game Theory / Minimax DP (Stone Game, Predict the Winner)

Built on

Interval DPTwo players take turns on one range of items, and each cell keeps the score difference for the player to move.

The problem

Predict the Winner (LC 486)(opens leetcode.com)

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.

Return true when Player 1 finishes with no less than Player 2 (equal totals also give true), and false otherwise.

Example 1

Input:nums = [1,5,2]

Output:false

Player 2 always gets the 5: once Player 1 takes 1 or 2, the 5 sits at an end. Player 1 ends with 3 against 5.

Minimax DP

shared game state ➔ my gain minus the opponent's best reply ➔ score difference

Minimax DP

Python

1	def predict_the_winner(nums: list[int]) -> bool:
2	"""Predict the Winner: minimax DP on the lead of whoever moves next on nums[i..j].
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(nums)
6	# diff: diff[i][j] is the most the player to move next can end ahead on nums[i..j]
7	diff = [[0] * n for _ in range(n)]
8
9	for i in range(n - 1, -1, -1):
10	# 1. Fill Bottom Row Up:
11	# diff[i + 1][j] must be final before diff[i][j] reads it, so i counts down from n - 1.
12	diff[i][i] = nums[i]
13	for j in range(i + 1, n):
14	# 2. Weigh Each Move Against The Opponent's Best Reply:
15	# Taking nums[i] hands nums[i + 1..j] to the opponent, who then leads by diff[i + 1][j];
16	# that lead counts against the mover, so it is subtracted, not added. take_right mirrors it.
17	take_left = nums[i] - diff[i + 1][j]
18	take_right = nums[j] - diff[i][j - 1]
19	diff[i][j] = max(take_left, take_right)
20
21	# A tie counts as a win for Player 1, so a non-negative final lead is a win.
22	return diff[0][n - 1] >= 0

Invariant: 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.

See it run

Minimax DP on [1, 5, 2], step by step

i 2

Rows are i and columns are j, written as index:nums[index].

write the range being written
diff[i+1][j] the range left after taking the left end
diff[i][j-1] the range left after taking the right end
answer the final result

diff[i][j] is the most the player to move can end ahead on nums[i..j]. The table for nums = [1, 5, 2] is empty.

0:1

1:5

2:2

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Adding the opponent's lead instead of subtracting it
Mistake
```
take_left = nums[i] + diff[i + 1][j]
take_right = nums[j] + diff[i][j - 1]
```
Fix
```
take_left = nums[i] - diff[i + 1][j]
take_right = nums[j] - diff[i][j - 1]
```
What happens: After you take nums[i], the opponent moves on nums[i + 1..j]. diff[i + 1][j] is the opponent's lead there, so it counts against you. Adding it makes every lead positive. So Player 1 always seems to win.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 2: Taking the bigger end on every move
Mistake
```
scores[turn] += max(nums[lo], nums[hi])
```
Fix
```
diff[i][j] = max(take_left, take_right)
```
What happens: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], taking 7 lets the opponent take 233. Taking 1 wins, and only nums[0] - diff[1][3] shows it.
Example: nums = [1, 5, 233, 7]
Mistake: returns FalseFix: returns True
Gotcha 3: Returning diff[0][n - 1] > 0 instead of >= 0
Mistake
```
return diff[0][n - 1] > 0
```
Fix
```
return diff[0][n - 1] >= 0
```
What happens: The problem counts a tie as a win for Player 1. A tie gives diff[0][n - 1] == 0. > 0 returns False for it.
Example: nums = [2, 4, 2] (a 4-4 tie)
Mistake: returns FalseFix: returns True
Gotcha 4: Filling i upward from 0
Mistake
```
for i in range(n):
```
Fix
```
for i in range(n - 1, -1, -1):
```
What happens: diff[i][j] reads diff[i + 1][j], a row further down. Filling from i = 0 reads that row while it still holds 0. So each move is valued as if the opponent gained nothing.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 5: Leaving out diff[i][i] = nums[i]
Mistake
```
for j in range(i + 1, n):
```
Fix
```
diff[i][i] = nums[i]
for j in range(i + 1, n):
```
What happens: A range with one number has no reply to subtract. The mover takes it, so diff[i][i] = nums[i]. Without that line, every one-number range reads as 0. Every longer range is built on those wrong values.
Example: nums = [1, 3, 2]
Mistake: returns FalseFix: returns True

Not this one if…

Only one player acts and every item in the range must be handled, as in Burst Balloons (LC 312): you choose a split point for your own best total, and there is no opponent's reply to subtract. See Burst Balloons

Deep Dive

Why one table describes both players

In a two-player game, a position can be valued from the side of the player who moves next. diff[i][j] is the most that player can end ahead of the other player on nums[i..j].

This replaces two tables (one score for each player) with one number per range. The number is a difference, so it already contains the opponent's score.

Why the opponent's lead is subtracted

Suppose the mover takes nums[i]. The range nums[i + 1..j] remains, and now the opponent is the player to move. The opponent can end ahead by diff[i + 1][j] on it.

The fill order and a worked table

The range order is the same as in Interval DP. Here the two cells that are read are diff[i + 1][j] and diff[i][j - 1], which are the ranges left after each possible move.

A tie counts as a win for Player 1 in Predict the Winner (LC 486), so the test is diff[0][n - 1] >= 0.

The cost, and a special case

A state is a range (i, j) with i <= j, so there are about N^2 / 2 states. Each does two subtractions and one max, which is constant work. The time is O(N^2) and the table takes O(N^2) space.

The table can be reduced to one row of O(N) space, because row i reads only row i + 1 and the same row.

60-Second Pitch

Common Questions

Why does a greedy choice of the bigger end fail?: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], greedy takes 7 and the opponent then takes 233. The best first move is 1. The opponent then faces [5, 233, 7] and takes 5 or 7, so Player 1 takes 233. The final lead of Player 1 is 222. The table finds this because it includes the opponent's best reply.
Why is the same recurrence used for both players?: The table stores a difference from the view of the player to move. Both players want the largest difference for themselves, so the rule is the same. After a move, the roles swap, and the next value is subtracted. This is why diff[i + 1][j] has a minus sign.
What is the complexity, and can the space be reduced?: The time is O(N^2) because there are about N^2 / 2 ranges with constant work each. The table takes O(N^2) space. Row i reads only row i + 1 and its own earlier columns, so one array of size N is enough for O(N) space.
How does this change for Stone Game (LC 877) or Stone Game II (LC 1140)?: Stone Game (LC 877) has an even number of piles, so the first player always wins, and the table only confirms it. Stone Game II (LC 1140) adds a rule that a move may take up to 2 * m piles, where m is a parameter. The state becomes (i, m), and the same idea applies: the mover's total is the remaining sum minus the opponent's best result.
How do you handle a game where the players do not both maximize a score?: If the game has only win or loss, store a boolean: a position is winning when at least one move leads to a losing position for the opponent. If the score is shared but opposed, the difference form in this card is correct. If the players have different goals, a single table does not apply, and you need one value for each player.

SWE Reasoning

Spot it

Two players take turns on the same shared state, such as a row of numbers or a pile of stones.
Both players play perfectly. The question asks who wins, or by how much.
The values on a move can be added to a score, so the result can be written as a difference of scores.
A move leaves a smaller game of the same kind, such as a shorter range. This gives states (i, j).
A greedy rule, such as taking the bigger end, is tempting. A short counter-example usually shows that it fails.

The invariant, step by step

diff is an n by n table. Row i is processed from i = n - 1 down to 0.
For a range of one number, diff[i][i] = nums[i]: the mover takes it, and the opponent gets nothing.
For j > i, the mover can take nums[i] or nums[j].
After taking nums[i], the opponent moves on nums[i + 1..j] and leads by diff[i + 1][j]. This range is shorter, so it was filled earlier and is final.
The result of this choice for the mover is take_left = nums[i] - diff[i + 1][j]. The other choice is take_right = nums[j] - diff[i][j - 1].
The mover plays the better choice, so diff[i][j] = max(take_left, take_right).
The whole game is diff[0][n - 1]. Player 1 wins when it is at least 0.

Traps

Two tables that are not linked. Keeping a score for each player and maximizing only Player 1's score ignores that Player 2 also plays the best move. Use one table of differences.
Using the even-length shortcut on an odd length. For an even number of piles, the first player never loses, as in Stone Game (LC 877). Predict the Winner (LC 486) allows any length. For nums = [1, 5, 2], the shortcut returns True, but the correct answer is False.
Recursion without a stored table. The plain recursion on (i, j) repeats ranges. For 20 numbers it makes 2,097,151 calls, while the table has only 210 ranges. Store each range once.

Practice

Canonical LeetCode:Predict the Winner (LC 486)Stone Game VII (LC 1690)Stone Game III (LC 1406)Stone Game II (LC 1140)

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P3MediumBuilt on Interval DP~3 min speedrun

Game Theory / Minimax DP (Stone Game, Predict the Winner)

Built on

Interval DPTwo players take turns on one range of items, and each cell keeps the score difference for the player to move.

The problem

Predict the Winner (LC 486)(opens leetcode.com)

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.

Return true when Player 1 finishes with no less than Player 2 (equal totals also give true), and false otherwise.

Example 1

Input:nums = [1,5,2]

Output:false

Player 2 always gets the 5: once Player 1 takes 1 or 2, the 5 sits at an end. Player 1 ends with 3 against 5.

Minimax DP

shared game state ➔ my gain minus the opponent's best reply ➔ score difference

Minimax DP

Python

1	def predict_the_winner(nums: list[int]) -> bool:
2	"""Predict the Winner: minimax DP on the lead of whoever moves next on nums[i..j].
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(nums)
6	# diff: diff[i][j] is the most the player to move next can end ahead on nums[i..j]
7	diff = [[0] * n for _ in range(n)]
8
9	for i in range(n - 1, -1, -1):
10	# 1. Fill Bottom Row Up:
11	# diff[i + 1][j] must be final before diff[i][j] reads it, so i counts down from n - 1.
12	diff[i][i] = nums[i]
13	for j in range(i + 1, n):
14	# 2. Weigh Each Move Against The Opponent's Best Reply:
15	# Taking nums[i] hands nums[i + 1..j] to the opponent, who then leads by diff[i + 1][j];
16	# that lead counts against the mover, so it is subtracted, not added. take_right mirrors it.
17	take_left = nums[i] - diff[i + 1][j]
18	take_right = nums[j] - diff[i][j - 1]
19	diff[i][j] = max(take_left, take_right)
20
21	# A tie counts as a win for Player 1, so a non-negative final lead is a win.
22	return diff[0][n - 1] >= 0

Invariant: 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.

See it run

Minimax DP on [1, 5, 2], step by step

i 2

Rows are i and columns are j, written as index:nums[index].

write the range being written
diff[i+1][j] the range left after taking the left end
diff[i][j-1] the range left after taking the right end
answer the final result

diff[i][j] is the most the player to move can end ahead on nums[i..j]. The table for nums = [1, 5, 2] is empty.

0:1

1:5

2:2

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Adding the opponent's lead instead of subtracting it
Mistake
```
take_left = nums[i] + diff[i + 1][j]
take_right = nums[j] + diff[i][j - 1]
```
Fix
```
take_left = nums[i] - diff[i + 1][j]
take_right = nums[j] - diff[i][j - 1]
```
What happens: After you take nums[i], the opponent moves on nums[i + 1..j]. diff[i + 1][j] is the opponent's lead there, so it counts against you. Adding it makes every lead positive. So Player 1 always seems to win.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 2: Taking the bigger end on every move
Mistake
```
scores[turn] += max(nums[lo], nums[hi])
```
Fix
```
diff[i][j] = max(take_left, take_right)
```
What happens: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], taking 7 lets the opponent take 233. Taking 1 wins, and only nums[0] - diff[1][3] shows it.
Example: nums = [1, 5, 233, 7]
Mistake: returns FalseFix: returns True
Gotcha 3: Returning diff[0][n - 1] > 0 instead of >= 0
Mistake
```
return diff[0][n - 1] > 0
```
Fix
```
return diff[0][n - 1] >= 0
```
What happens: The problem counts a tie as a win for Player 1. A tie gives diff[0][n - 1] == 0. > 0 returns False for it.
Example: nums = [2, 4, 2] (a 4-4 tie)
Mistake: returns FalseFix: returns True
Gotcha 4: Filling i upward from 0
Mistake
```
for i in range(n):
```
Fix
```
for i in range(n - 1, -1, -1):
```
What happens: diff[i][j] reads diff[i + 1][j], a row further down. Filling from i = 0 reads that row while it still holds 0. So each move is valued as if the opponent gained nothing.
Example: nums = [1, 5, 2]
Mistake: returns TrueFix: returns False
Gotcha 5: Leaving out diff[i][i] = nums[i]
Mistake
```
for j in range(i + 1, n):
```
Fix
```
diff[i][i] = nums[i]
for j in range(i + 1, n):
```
What happens: A range with one number has no reply to subtract. The mover takes it, so diff[i][i] = nums[i]. Without that line, every one-number range reads as 0. Every longer range is built on those wrong values.
Example: nums = [1, 3, 2]
Mistake: returns FalseFix: returns True

Not this one if…

Only one player acts and every item in the range must be handled, as in Burst Balloons (LC 312): you choose a split point for your own best total, and there is no opponent's reply to subtract. See Burst Balloons

Deep Dive

Why one table describes both players

In a two-player game, a position can be valued from the side of the player who moves next. diff[i][j] is the most that player can end ahead of the other player on nums[i..j].

This replaces two tables (one score for each player) with one number per range. The number is a difference, so it already contains the opponent's score.

Why the opponent's lead is subtracted

Suppose the mover takes nums[i]. The range nums[i + 1..j] remains, and now the opponent is the player to move. The opponent can end ahead by diff[i + 1][j] on it.

The fill order and a worked table

The range order is the same as in Interval DP. Here the two cells that are read are diff[i + 1][j] and diff[i][j - 1], which are the ranges left after each possible move.

A tie counts as a win for Player 1 in Predict the Winner (LC 486), so the test is diff[0][n - 1] >= 0.

The cost, and a special case

A state is a range (i, j) with i <= j, so there are about N^2 / 2 states. Each does two subtractions and one max, which is constant work. The time is O(N^2) and the table takes O(N^2) space.

The table can be reduced to one row of O(N) space, because row i reads only row i + 1 and the same row.

60-Second Pitch

Common Questions

Why does a greedy choice of the bigger end fail?: The bigger end can open a much bigger number for the opponent. On [1, 5, 233, 7], greedy takes 7 and the opponent then takes 233. The best first move is 1. The opponent then faces [5, 233, 7] and takes 5 or 7, so Player 1 takes 233. The final lead of Player 1 is 222. The table finds this because it includes the opponent's best reply.
Why is the same recurrence used for both players?: The table stores a difference from the view of the player to move. Both players want the largest difference for themselves, so the rule is the same. After a move, the roles swap, and the next value is subtracted. This is why diff[i + 1][j] has a minus sign.
What is the complexity, and can the space be reduced?: The time is O(N^2) because there are about N^2 / 2 ranges with constant work each. The table takes O(N^2) space. Row i reads only row i + 1 and its own earlier columns, so one array of size N is enough for O(N) space.
How does this change for Stone Game (LC 877) or Stone Game II (LC 1140)?: Stone Game (LC 877) has an even number of piles, so the first player always wins, and the table only confirms it. Stone Game II (LC 1140) adds a rule that a move may take up to 2 * m piles, where m is a parameter. The state becomes (i, m), and the same idea applies: the mover's total is the remaining sum minus the opponent's best result.
How do you handle a game where the players do not both maximize a score?: If the game has only win or loss, store a boolean: a position is winning when at least one move leads to a losing position for the opponent. If the score is shared but opposed, the difference form in this card is correct. If the players have different goals, a single table does not apply, and you need one value for each player.

SWE Reasoning

Spot it

Two players take turns on the same shared state, such as a row of numbers or a pile of stones.
Both players play perfectly. The question asks who wins, or by how much.
The values on a move can be added to a score, so the result can be written as a difference of scores.
A move leaves a smaller game of the same kind, such as a shorter range. This gives states (i, j).
A greedy rule, such as taking the bigger end, is tempting. A short counter-example usually shows that it fails.

The invariant, step by step

diff is an n by n table. Row i is processed from i = n - 1 down to 0.
For a range of one number, diff[i][i] = nums[i]: the mover takes it, and the opponent gets nothing.
For j > i, the mover can take nums[i] or nums[j].
After taking nums[i], the opponent moves on nums[i + 1..j] and leads by diff[i + 1][j]. This range is shorter, so it was filled earlier and is final.
The result of this choice for the mover is take_left = nums[i] - diff[i + 1][j]. The other choice is take_right = nums[j] - diff[i][j - 1].
The mover plays the better choice, so diff[i][j] = max(take_left, take_right).
The whole game is diff[0][n - 1]. Player 1 wins when it is at least 0.

Traps

Two tables that are not linked. Keeping a score for each player and maximizing only Player 1's score ignores that Player 2 also plays the best move. Use one table of differences.
Using the even-length shortcut on an odd length. For an even number of piles, the first player never loses, as in Stone Game (LC 877). Predict the Winner (LC 486) allows any length. For nums = [1, 5, 2], the shortcut returns True, but the correct answer is False.
Recursion without a stored table. The plain recursion on (i, j) repeats ranges. For 20 numbers it makes 2,097,151 calls, while the table has only 210 ranges. Store each range once.

Practice

Canonical LeetCode:Predict the Winner (LC 486)Stone Game VII (LC 1690)Stone Game III (LC 1406)Stone Game II (LC 1140)