Stone Game LeetCode 877 Guide

LeetCode 877 — Stone Game — presents a two-player game. An even number of piles of stones are arranged in a row with piles[i] stones in the i-th pile. Alice and Bob take turns, with Alice going first. On each turn, a player takes the entire pile from either the left end or the right end of the row. The player with the most stones wins.

The problem guarantees an even number of piles and that the total number of stones is odd, so there are no ties. Both players play optimally. Your task is to determine whether Alice (the first player) wins.

This problem has two solutions: a mathematical proof that Alice always wins (return true), and a general interval DP that works for any variant. Understanding both is essential — interviewers often ask for the DP even after you spot the math trick.

With an even number of piles, Alice can always choose to take all odd-indexed piles or all even-indexed piles. Here is why: color the piles alternating black and white. If Alice takes from the left, the new left pile is the opposite color. If she takes from the right, the new left and right are still predictable.

More concretely, Alice can compute the sum of odd-indexed piles and the sum of even-indexed piles before the game starts. One sum must be strictly larger (since total is odd). Alice can then follow a strategy that guarantees she collects all piles from the larger-sum group.

This means Alice always wins. The solution is literally return true. However, this only works because the number of piles is even. For odd piles or other variants (Stone Game II, III, IV), you need the DP approach.

Define dp[i][j] as the maximum score advantage the current player can achieve over the opponent considering piles[i..j]. The current player picks either piles[i] or piles[j], then becomes the opponent for the remaining subproblem.

If the current player takes piles[i], the remaining subproblem is piles[i+1..j] where the opponent is now the current player. The advantage is piles[i] - dp[i+1][j] (subtract because the opponent's advantage becomes your disadvantage). Similarly for taking piles[j]: advantage is piles[j] - dp[i][j-1].

The recurrence is dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]). Base case: dp[i][i] = piles[i] (only one pile, take it). Alice wins if dp[0][n-1] > 0. This formulation elegantly handles the alternating-turn structure.

Consider piles = [5, 3, 4, 5]. Base cases: dp[0][0]=5, dp[1][1]=3, dp[2][2]=4, dp[3][3]=5. Now fill diagonals of increasing length.

Length 2: dp[0][1] = max(5-3, 3-5) = max(2, -2) = 2. dp[1][2] = max(3-4, 4-3) = max(-1, 1) = 1. dp[2][3] = max(4-5, 5-4) = max(-1, 1) = 1.

Length 3: dp[0][2] = max(5-dp[1][2], 4-dp[0][1]) = max(5-1, 4-2) = max(4, 2) = 4. dp[1][3] = max(3-dp[2][3], 5-dp[1][2]) = max(3-1, 5-1) = max(2, 4) = 4. Length 4: dp[0][3] = max(5-dp[1][3], 5-dp[0][2]) = max(5-4, 5-4) = 1. Since dp[0][3] = 1 > 0, Alice wins.

The one-line solution is trivially return True (Python) or return true (Java). For the DP version in Python, create a 2D list dp of size n x n. Fill the diagonal dp[i][i] = piles[i], then iterate over increasing gap lengths from 1 to n-1.

In Java, use an int[][] of size n x n. The nested loop structure is: outer loop for gap length (1 to n-1), inner loop for starting index i (0 to n-1-gap), with j = i + gap. Apply the recurrence at each cell.

Space optimization: since each diagonal only depends on the previous diagonal, you can compress to a 1D array. Iterate gap lengths and update in-place. This reduces space from O(n^2) to O(n) while maintaining O(n^2) time.

The math solution runs in O(1) time and O(1) space — just return true. This is optimal but only works for the specific constraints of LeetCode 877 (even piles, odd total).

The interval DP runs in O(n^2) time and O(n^2) space. There are O(n^2) subproblems (all intervals [i, j]), each computed in O(1) time. With the 1D optimization, space drops to O(n).

For the general Stone Game variants, O(n^2) is optimal because you must consider all O(n^2) possible intervals. No known algorithm solves the general two-player optimal play problem faster than quadratic for arbitrary pile values.

Stone Game II (LeetCode 1140) extends the problem by allowing players to take 1 to 2M piles from one end, where M grows. Stone Game III (LeetCode 1406) allows taking 1, 2, or 3 piles. Both require modified DP states but share the same minimax core.

Predict the Winner (LeetCode 486) is essentially the same problem as Stone Game but without the even-pile guarantee. The interval DP solution works identically. This is a great follow-up to verify your DP implementation handles odd-length arrays.

For other game theory problems, try Nim Game (LeetCode 292) for a simpler math-based game, and Flip Game II (LeetCode 294) for a backtracking approach to game solving. Together with the Stone Game family, these cover the full spectrum of game theory on LeetCode.