Stone Game
Problem Statement
Alice and Bob take turns removing an entire pile of stones from either the left end or the right end of a row. Alice moves first. Both players play optimally, and the total number of stones is odd so there cannot be a tie. Return whether Alice wins.
Input
An integer array piles, where piles[i] is the number of stones in the i-th pile.
Output
A boolean: true if Alice can finish with more stones than Bob, otherwise false.
Constraints
- •
2 <= piles.length <= 500 - •
piles.length is even - •
1 <= piles[i] <= 500 - •
sum(piles) is odd
Examples
Example 1
piles = [5,3,4,5]
trueExample 2
piles = [3,7,2,3]
trueLearning Objectives
- Model a two-player optimal game as a score difference instead of tracking both totals separately.
- Understand why subtracting the next state captures the opponent becoming the current player.
- Use interval DP for games where choices remove items from the ends.
- Distinguish the LeetCode parity shortcut from the reusable DP technique.
Intuition
For this specific problem, there is a famous parity observation: because the number of piles is even, Alice can commit to taking either all originally even-indexed piles or all originally odd-indexed piles, whichever has the larger total. That proves Alice always wins.
But that shortcut is narrow. The interview-useful technique is a game DP that works even when constraints change. Instead of storing Alice score and Bob score, store one number: the best score difference the player to move can achieve from the current interval.
If the current player takes the left pile, they gain piles[left] immediately. Then the opponent becomes the current player on the smaller interval and can achieve dp[left + 1][right] advantage over us. So our net difference for taking left is piles[left] - dp[left + 1][right]. The same logic applies to taking the right pile. Choose the better of the two.
Common mistakes
- ×Returning true only because of the parity shortcut without being able to derive the general recurrence.
- ×Trying to store absolute Alice and Bob totals, which makes turns and perspective harder to manage.
- ×Forgetting that **dp[i][j]** is from the current player's perspective, not always Alice's perspective.
- ×Adding the future DP value instead of subtracting it; the future advantage belongs to the opponent.
- ×Using greedy larger-end selection, which is not reliable in adversarial games.
State Definition
Let dp[left][right] be the maximum score difference the current player can achieve over the other player using only piles from index left through right. A positive value means the player whose turn it is can finish ahead by that many stones from this interval.
State Transition
The current player has two choices:
- Take piles[left], then the opponent plays optimally on left + 1..right, producing a future advantage of dp[left + 1][right] against the current player.
- Take piles[right], then the opponent plays optimally on left..right - 1, producing dp[left][right - 1] against the current player.
Therefore:
dp[left][right] = max(piles[left] - dp[left + 1][right], piles[right] - dp[left][right - 1])
Base case: dp[i][i] = piles[i], because the current player takes the only pile. Alice wins when dp[0][n - 1] > 0.
Solutions
Solution: Interval DP with score difference
Use this for take-from-ends games where both players are optimal. The score-difference state removes the need for a separate turn dimension.
Build intervals from length 1 upward. For each interval, compute the best net advantage from taking the left end or the right end. Because the next state is from the opponent's perspective, subtract that state from the stones just taken.
Step-by-step
- Initialise dp[i][i] to piles[i].
- Increase interval length from 2 to n.
- For each interval, compute the net result of taking the left pile and the net result of taking the right pile.
- Store the larger difference.
- Return whether the full interval difference is positive.
O(n^2)
O(n^2)
Every interval is solved once and each state does O(1) work.
Java implementation
Dry Run
Sample input
piles = [5,3,4,5]. Each cell stores the best score difference for the player to move on that interval.
| interval | take left | take right | dp difference | meaning |
|---|---|---|---|---|
| [0,1] = [5,3] | 5 - 3 = 2 | 3 - 5 = -2 | 2 | current player wins this interval by 2 |
| [1,2] = [3,4] | 3 - 4 = -1 | 4 - 3 = 1 | 1 | current player prefers the right pile |
| [2,3] = [4,5] | 4 - 5 = -1 | 5 - 4 = 1 | 1 | current player prefers the right pile |
| [0,2] = [5,3,4] | 5 - 1 = 4 | 4 - 2 = 2 | 4 | best advantage is 4 |
| [1,3] = [3,4,5] | 3 - 1 = 2 | 5 - 1 = 4 | 4 | best advantage is 4 |
| [0,3] = [5,3,4,5] | 5 - 4 = 1 | 5 - 4 = 1 | 1 | Alice wins by 1 |
The full interval has positive difference 1, so Alice can force more stones than Bob. The parity shortcut also says Alice wins, but the DP explains how optimal play is evaluated.
Complexity Analysis
The DP is O(n^2), even though this exact LeetCode version can be answered in O(1) using parity. The DP is the reusable solution for variants without the parity guarantee.
Interval DP with score difference
O(n^2)
O(n^2)
Every interval is solved once and each state does O(1) work.
Interview Tips
Mention the parity proof briefly, then say you will implement the general game-theory DP because it survives follow-up changes. Emphasise that dp is always from the current player's perspective; that is why the recurrence subtracts the next state.
Likely follow-ups
- How would the solution change if the number of piles were odd and ties were possible?
- Can you reduce the interval table to O(n) space?
- What if a player could take one or two piles from either end?
- How would you return the first move Alice should make under optimal play?
Similar Problems
Key Takeaways
- For two-player optimal games, score difference is often cleaner than two separate totals.
- The next DP state is subtracted because it is the opponent's advantage after the current move.
- End-picking games naturally form interval DP states.
- Know the parity shortcut, but lead with the general recurrence for interviews.