LeetCode 877 - Stone Game
The problem describes a two-player game played on an array of stone piles. Each pile contains a positive number of stones, and the piles are arranged in a row. Alice and Bob alternate turns, with Alice always moving first.
Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Game Theory
Solution
Problem Understanding
The problem describes a two-player game played on an array of stone piles. Each pile contains a positive number of stones, and the piles are arranged in a row. Alice and Bob alternate turns, with Alice always moving first. On each turn, the current player may only take the pile from the left end or the right end of the row. The chosen pile is removed permanently, and the player adds those stones to their score.
The goal is to determine whether Alice can guarantee a win assuming both players play optimally. Since the total number of stones is guaranteed to be odd, ties are impossible. The function should therefore return true if Alice can end with more stones than Bob, otherwise false.
The input is an integer array piles, where piles[i] represents the number of stones in the i-th pile. The length of the array is always even, which is important because both players will take the same number of turns. The constraints allow up to 500 piles, which immediately tells us that an exponential brute-force search will be too slow.
Several important guarantees simplify the problem:
- The number of piles is always even.
- Every pile contains a positive number of stones.
- The total number of stones is odd, so a tie cannot occur.
- Both players always play optimally.
A naive implementation can easily fail when trying to model future decisions greedily. For example, taking the larger of the two ends at every step is not always optimal because a smaller immediate choice may force the opponent into a worse future position. The solution therefore requires reasoning about optimal play across multiple turns.
An interesting detail is that this specific LeetCode problem has a mathematical property: Alice always wins when both players play optimally. However, understanding the dynamic programming formulation is still valuable because it teaches the general game-theory pattern used in many interval DP problems.
Approaches
Brute Force Approach
The brute-force solution explores every possible sequence of moves. At each turn, the current player has two choices:
- Take the leftmost pile
- Take the rightmost pile
The recursion continues until no piles remain. For every state, the algorithm computes the best possible outcome assuming the opponent also plays optimally.
This approach is correct because it explicitly examines all possible game states and optimal responses. However, it is extremely inefficient because the same subproblems are recomputed many times. The number of game states grows exponentially, approximately O(2^n), which becomes infeasible when n can reach 500.
Optimal Dynamic Programming Approach
The key insight is that the game has overlapping subproblems. A game state is completely determined by the current interval [left, right].
Instead of storing the total score directly, we store the score difference the current player can achieve over the opponent for a given interval.
Define:
dp[left][right]= maximum score difference the current player can achieve from pilesleftthroughright
If the current player chooses the left pile:
piles[left] - dp[left + 1][right]
The subtraction appears because after taking a pile, the opponent becomes the current player for the remaining interval.
Similarly, if the player chooses the right pile:
piles[right] - dp[left][right - 1]
The optimal choice is the maximum of these two values.
At the end:
- If
dp[0][n - 1] > 0, Alice can guarantee more stones than Bob.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Explores every possible game sequence recursively |
| Optimal Dynamic Programming | O(n²) | O(n²) | Stores interval results and avoids recomputation |
Algorithm Walkthrough
- Create a two-dimensional DP table where
dp[left][right]represents the maximum score difference the current player can achieve over the opponent using piles between indicesleftandright. - Initialize the base cases where
left == right. If only one pile remains, the current player takes it immediately, so:
dp[i][i] = piles[i]
- Process intervals in increasing order of length. This ordering is important because larger intervals depend on smaller intervals already being computed.
- For each interval
[left, right], compute the result of taking the left pile:
take_left = piles[left] - dp[left + 1][right]
The subtraction works because after the current player takes the left pile, the opponent plays optimally on the remaining interval. 5. Compute the result of taking the right pile:
take_right = piles[right] - dp[left][right - 1]
- Store the better of the two choices:
dp[left][right] = max(take_left, take_right)
- After filling the table, check the final interval:
dp[0][n - 1]
If this value is positive, Alice can guarantee a higher score than Bob.
Why it works
The DP state always represents the best possible score advantage the current player can force from a subarray. Every move transitions into a smaller subproblem where the opponent becomes the current player. Because the recurrence models both players acting optimally, the computed result correctly represents perfect play. By evaluating every interval bottom-up, the algorithm guarantees that all required subproblems are already solved before they are used.
Python Solution
from typing import List
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
n = len(piles)
dp = [[0] * n for _ in range(n)]
# Base case: one pile remaining
for i in range(n):
dp[i][i] = piles[i]
# Build solutions for larger intervals
for length in range(2, n + 1):
for left in range(n - length + 1):
right = left + length - 1
take_left = piles[left] - dp[left + 1][right]
take_right = piles[right] - dp[left][right - 1]
dp[left][right] = max(take_left, take_right)
return dp[0][n - 1] > 0
The implementation begins by creating a DP table of size n x n. Each cell stores the best score difference the current player can achieve for a particular interval.
The diagonal entries are initialized first because intervals of length one are the simplest possible subproblems. If only one pile exists, the current player takes it immediately.
The algorithm then processes intervals in increasing order of length. This ordering ensures that when computing dp[left][right], the smaller intervals dp[left + 1][right] and dp[left][right - 1] have already been solved.
For every interval, the code evaluates both possible moves:
- Taking the left pile
- Taking the right pile
The opponent's optimal response is represented by subtracting the corresponding DP value. The current player chooses whichever move produces the larger score advantage.
Finally, the algorithm checks whether Alice can force a positive score difference over Bob across the entire array.
Go Solution
func stoneGame(piles []int) bool {
n := len(piles)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
// Base case: single pile
for i := 0; i < n; i++ {
dp[i][i] = piles[i]
}
// Build intervals of increasing length
for length := 2; length <= n; length++ {
for left := 0; left <= n-length; left++ {
right := left + length - 1
takeLeft := piles[left] - dp[left+1][right]
takeRight := piles[right] - dp[left][right-1]
if takeLeft > takeRight {
dp[left][right] = takeLeft
} else {
dp[left][right] = takeRight
}
}
}
return dp[0][n-1] > 0
}
The Go implementation follows the same DP logic as the Python version. The primary difference is manual slice allocation for the two-dimensional DP table.
Go arrays are fixed-size, so slices are used for flexibility. Since all values remain well within Go's int range, integer overflow is not a concern under the given constraints.
Unlike Python, Go does not provide a built-in max function for integers, so the implementation uses an explicit conditional comparison.
Worked Examples
Example 1
Input:
piles = [5, 3, 4, 5]
Initial DP diagonal:
| Interval | Value |
|---|---|
| dp[0][0] | 5 |
| dp[1][1] | 3 |
| dp[2][2] | 4 |
| dp[3][3] | 5 |
Length = 2
| Interval | take_left | take_right | dp |
|---|---|---|---|
| [0,1] | 5 - 3 = 2 | 3 - 5 = -2 | 2 |
| [1,2] | 3 - 4 = -1 | 4 - 3 = 1 | 1 |
| [2,3] | 4 - 5 = -1 | 5 - 4 = 1 | 1 |
Length = 3
| Interval | take_left | take_right | dp |
|---|---|---|---|
| [0,2] | 5 - 1 = 4 | 4 - 2 = 2 | 4 |
| [1,3] | 3 - 1 = 2 | 5 - 1 = 4 | 4 |
Length = 4
| Interval | take_left | take_right | dp |
|---|---|---|---|
| [0,3] | 5 - 4 = 1 | 5 - 4 = 1 | 1 |
Final result:
dp[0][3] = 1 > 0
Alice wins.
Example 2
Input:
piles = [3, 7, 2, 3]
Initial diagonal:
| Interval | Value |
|---|---|
| dp[0][0] | 3 |
| dp[1][1] | 7 |
| dp[2][2] | 2 |
| dp[3][3] | 3 |
Length = 2
| Interval | take_left | take_right | dp |
|---|---|---|---|
| [0,1] | 3 - 7 = -4 | 7 - 3 = 4 | 4 |
| [1,2] | 7 - 2 = 5 | 2 - 7 = -5 | 5 |
| [2,3] | 2 - 3 = -1 | 3 - 2 = 1 | 1 |
Length = 3
| Interval | take_left | take_right | dp |
|---|---|---|---|
| [0,2] | 3 - 5 = -2 | 2 - 4 = -2 | -2 |
| [1,3] | 7 - 1 = 6 | 3 - 5 = -2 | 6 |
Length = 4
| Interval | take_left | take_right | dp |
|---|---|---|---|
| [0,3] | 3 - 6 = -3 | 3 - (-2) = 5 | 5 |
Final result:
dp[0][3] = 5 > 0
Alice wins.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n²) | Every interval is computed exactly once |
| Space | O(n²) | The DP table stores results for all intervals |
The DP table contains n² states because every pair (left, right) represents a possible interval. Each state is computed in constant time using previously solved subproblems. Therefore, the total running time is quadratic.
The memory usage is also quadratic because the algorithm stores the result for every interval in the two-dimensional table.
Test Cases
from typing import List
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
n = len(piles)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = piles[i]
for length in range(2, n + 1):
for left in range(n - length + 1):
right = left + length - 1
take_left = piles[left] - dp[left + 1][right]
take_right = piles[right] - dp[left][right - 1]
dp[left][right] = max(take_left, take_right)
return dp[0][n - 1] > 0
solution = Solution()
assert solution.stoneGame([5, 3, 4, 5]) is True # Provided example 1
assert solution.stoneGame([3, 7, 2, 3]) is True # Provided example 2
assert solution.stoneGame([1, 2]) is True # Smallest valid input
assert solution.stoneGame([2, 1]) is True # Alice immediately takes larger pile
assert solution.stoneGame([1, 100, 3, 4]) is True # Large interior value
assert solution.stoneGame([8, 15, 3, 7]) is True # Classic optimal-play case
assert solution.stoneGame([1, 1, 1, 2]) is True # Near-equal values
assert solution.stoneGame([20, 30, 2, 2, 2, 10]) is True # Larger even-sized array
assert solution.stoneGame([4, 4, 4, 5]) is True # Repeated values with one larger pile
assert solution.stoneGame([100, 1, 1, 100]) is True # Symmetric high values
| Test | Why |
|---|---|
[5,3,4,5] |
Validates the first official example |
[3,7,2,3] |
Validates the second official example |
[1,2] |
Smallest possible valid input |
[2,1] |
Confirms Alice chooses the better edge |
[1,100,3,4] |
Ensures greedy behavior is not required |
[8,15,3,7] |
Classic interval game scenario |
[1,1,1,2] |
Tests repeated small values |
[20,30,2,2,2,10] |
Tests larger interval combinations |
[4,4,4,5] |
Tests mostly equal values |
[100,1,1,100] |
Tests symmetry and optimal choices |
Edge Cases
One important edge case is the minimum valid input size, where the array contains only two piles. In this situation, Alice simply chooses the larger pile and wins immediately. Some implementations incorrectly assume at least one recursive layer or interval expansion is necessary, but the DP initialization handles this naturally because the interval of length two is computed directly from the base cases.
Another important edge case involves repeated or nearly identical pile values, such as [4,4,4,5]. Naive greedy strategies may behave unpredictably when values are similar because choosing the locally larger pile does not always maximize the final score. The DP formulation correctly evaluates future consequences rather than immediate gains.
A third important edge case occurs when the largest pile is not located at either end initially, such as [1,100,3,4]. A simplistic approach might fail because the optimal move is determined by long-term positioning rather than immediate access to the largest value. The interval DP correctly models future turns and opponent responses, ensuring the optimal strategy is always selected.
Another subtle case is symmetric arrays like [100,1,1,100]. These can expose bugs in interval indexing or transition logic because both ends initially appear equivalent. Since the implementation systematically evaluates both choices using the same recurrence relation, symmetry is handled correctly without any special-case logic.