Community Problem
Stone Game
Difficulty: Medium
Decide whether the first player wins a take-from-either-end stone game on an even-length pile, with both players playing optimally.
Stone Game
Decide whether the first player wins a take-from-either-end stone game on an even-length pile, with both players playing optimally.
By @lunamitchell
May 13, 2026
·
Updated May 18, 2026
1,142 views
4
4.3 (13)
I had this on a Two Sigma onsite and the interviewer's follow-up was sneaky: "once you've coded the O(n^2) interval DP, can you tell me why the answer is always true?" The DP is the textbook walkthrough; the parity argument (color the indices like a chessboard, prove that the first player can always force the higher-sum color) is the trick that turns it into a one-line solution. The catalog covered predict-the-winner, but it skipped this even-length-piles variant where the parity shortcut applies.
Stone Game
Alice and Bob play a game with a row of piles, each containing a positive number of stones. The total number of stones across all piles is odd, and the number of piles is even. Players take turns, with Alice starting. Each turn a player picks the entire pile of stones from EITHER the very beginning OR the very end of the row. The player with the most stones at the end wins.
Assuming both players play optimally, return true if and only if Alice (the first player) wins.
Examples
Example 1:
- Input:
piles = [5, 3, 4, 5] - Output:
true - Explanation: Alice picks the 5 on the right (
piles[3]). Bob picks either 3 or 4; whichever, Alice picks the bigger remaining and ends with>= 11to Bob's<= 7.
Example 2:
- Input:
piles = [3, 7, 2, 3] - Output:
true - Explanation: Alice picks left (
3). Bob is now stuck choosing between3and2, leaving Alice the7.
Example 3:
- Input:
piles = [1, 100, 9, 1] - Output:
true - Explanation: Alice picks left (
1); Bob is forced into a choice that lets Alice grab the100.
Example 4:
- Input:
piles = [10, 1] - Output:
true - Explanation: Alice picks
10. Smallest possible game.
Constraints
2 <= piles.length <= 500.piles.lengthis even.1 <= piles[i] <= 500.- The sum of
piles[i]is odd (no ties possible).
Follow-up
Why is the answer always true under these constraints? Color the indices alternately white and black like a chessboard. Because the array length is even, the white-indexed sum and the black-indexed sum are different (the total is odd). Alice can ALWAYS take from the same color: on her first move, both ends have different colors, so she picks whichever color has the larger sum. After Alice picks, Bob faces an array whose ends have the SAME color (the one Alice didn't pick). Whichever Bob picks, Alice's next move again has both colors available at the ends, and she picks her color. By induction Alice ends up with all stones of her color and wins because that color has the strictly larger sum.
Solution
Hints
Solution Walkthrough
Approach: Interval DP on Score Difference (O(n^2) time, O(n^2) space)
Let dp[i][j] = the maximum SCORE DIFFERENCE (current player's stones minus opponent's stones) that the player to move can guarantee on subarray piles[i..j]. The recurrence is:
dp[i][i] = piles[i]
dp[i][j] = max( piles[i] - dp[i+1][j], // take left, opponent then plays optimally on [i+1..j]
piles[j] - dp[i][j-1] ) // take right, opponent then plays optimally on [i..j-1]The SUBTRACTION captures the alternating-turns structure: whatever score difference the opponent achieves on the smaller subarray works AGAINST us. Alice (the first player) wins iff dp[0][n-1] > 0.
Key Insight (the clever shortcut)
Under the problem constraints (piles.length is even, total is odd), Alice ALWAYS wins. The proof is a coloring argument: alternately color the indices white and black. Since the array length is even and the total is odd, the white-sum and black-sum are different. On her first move Alice picks the end whose color has the greater sum (the two ends have different colors). After her pick, Bob's two ends have the SAME color (the loser color); whatever Bob picks, Alice's NEXT move again has both colors at the ends and she picks her winner color. So Alice ends up with all stones of her color and wins.
This means return true is technically correct under the stated constraints. The DP solution is what the interviewer is fishing for; the parity shortcut is the follow-up answer.
Algorithm (the interview-canonical DP)
- Allocate
dp[n][n]withdp[i][i] = piles[i]. - For
lenfrom 2 ton:- For each interval
[i, i + len - 1], computedp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]).
- Return
dp[0][n-1] > 0.
Why It Works
The score-difference framing collapses the two-player optimization into a single recursion. Each player maximizes their own (current - other) value; subtracting the opponent's optimal future difference is correct because the opponent's gain is the current player's loss. By induction on interval length, dp[i][j] is exactly the score difference under optimal play from both sides.
Complexity
DP table
Intervals O(n^2)
Work per cell O(1)
Time O(n^2)
Space O(n^2) (can be reduced to O(n) with a rolling diagonal)Pitfalls
- Tracking Alice's score directly. Trying to keep
(aliceScore, bobScore)separately requires you to know whose turn it is, which doubles the state. The score-DIFFERENCE trick collapses both into one number. - Forgetting the subtraction.
dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])is the WRONG recurrence; it sums both players' choices into one pot. The minus sign encodes the adversarial alternation. - Iterating in row-major order. The recurrence reads
dp[i+1][j]anddp[i][j-1], both at SHORTER intervals. Iterate by interval length (or in reversei) so the predecessors are computed first.
Solution Code