LeetCode 877: Stone Game

Problem Restatement

Alice and Bob play a game with an even number of stone piles arranged in a row.

Each pile has a positive number of stones.

Alice moves first. On each turn, a player must take one entire pile from either the left end or the right end of the row.

The game ends when all piles are taken.

The player with more stones wins.

The total number of stones is odd, so the game cannot end in a tie. We need to return true if Alice wins when both players play optimally. LeetCode gives the constraints that the number of piles is even and the total number of stones is odd.

Input and Output

Example function shape:

def stoneGame(self, piles: list[int]) -> bool:
    ...

Examples

Example 1:

Input: piles = [5,3,4,5]
Output: true

Alice can win.

One possible play:

Alice has 9, Bob has 8, so Alice wins.

Example 2:

Input: piles = [2,1]
Output: true

Alice takes 2.

Bob takes 1.

Alice wins.

First Thought: Simulate Choices

At each turn, a player has two choices:

1. Take the left pile.
2. Take the right pile.

A naive recursive solution can try both choices for every turn.

But this creates many repeated subproblems. The same remaining interval of piles can be reached through different earlier choices.

For example, from:

[5,3,4,5]

After some choices, both players may reach the same middle interval:

[3,4]

So we should model the game by intervals.

Key Insight

The remaining game state is fully described by two indices:

i = left boundary
j = right boundary

So piles[i:j+1] is the current row of remaining piles.

Instead of tracking Alice and Bob separately, we track the score difference from the current player’s point of view.

Let:

dp[i][j] = maximum score difference the current player can achieve over the opponent using piles[i..j]

A positive value means the current player can end ahead.

A negative value means the current player will end behind.

When the current player chooses the left pile, they gain piles[i], then the opponent becomes the current player on interval i + 1 .. j.

The opponent can then achieve dp[i + 1][j] more than the current player from that smaller interval.

So the net difference for taking left is:

piles[i] - dp[i + 1][j]

Taking right gives:

piles[j] - dp[i][j - 1]

Therefore:

dp[i][j] = max(
    piles[i] - dp[i + 1][j],
    piles[j] - dp[i][j - 1]
)

Algorithm

Create a 2D table dp.

For a single pile, the current player takes it:

dp[i][i] = piles[i]

Then fill larger intervals by length.

For each interval [i, j]:

1. Compute the result if the current player takes the left pile.
2. Compute the result if the current player takes the right pile.
3. Store the better score difference.

At the end, dp[0][n - 1] is the best score difference Alice can force for the whole game.

If it is positive, Alice wins.

Correctness

The table entry dp[i][j] represents the maximum score difference the current player can force from the interval piles[i..j].

For the base case, when i == j, there is one pile left. The current player takes it, so the score difference is exactly piles[i].

For a larger interval, the current player has only two legal moves: take piles[i] or take piles[j].

If the current player takes piles[i], the opponent plays next on piles[i + 1..j]. Since dp[i + 1][j] is the opponent’s best score difference from that interval, the current player’s net advantage is piles[i] - dp[i + 1][j].

The same reasoning gives piles[j] - dp[i][j - 1] when taking the right pile.

The current player chooses the better of these two moves, so the recurrence computes the best possible score difference.

The table is filled from shorter intervals to longer intervals, so every needed smaller interval has already been computed.

Thus, dp[0][n - 1] gives Alice’s best possible score difference over Bob for the full game. If it is greater than zero, Alice wins.

Complexity

Implementation

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 i in range(n - length + 1):
                j = i + length - 1

                take_left = piles[i] - dp[i + 1][j]
                take_right = piles[j] - dp[i][j - 1]

                dp[i][j] = max(take_left, take_right)

        return dp[0][n - 1] > 0

Code Explanation

We create the table:

dp = [[0] * n for _ in range(n)]

dp[i][j] stores the best score difference the current player can force from piles[i] through piles[j].

The base case is:

for i in range(n):
    dp[i][i] = piles[i]

With one pile, the current player takes that pile.

Then we process intervals by length:

for length in range(2, n + 1):

This ensures smaller intervals are computed before larger intervals.

For each interval:

j = i + length - 1

The current player may take the left pile:

take_left = piles[i] - dp[i + 1][j]

Or the right pile:

take_right = piles[j] - dp[i][j - 1]

We store the better result:

dp[i][j] = max(take_left, take_right)

Finally:

return dp[0][n - 1] > 0

If Alice can force a positive score difference, Alice wins.

Mathematical Shortcut

For this specific LeetCode problem, Alice can always win.

The reason is that the number of piles is even. Alice can decide, on her first move, whether she wants to take all piles that originally had even indices or all piles that originally had odd indices.

Because the total sum is odd, one of those two groups has a larger total.

Alice can force herself to take the larger group by choosing the correct end on every turn.

So the accepted solution can be:

class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        return True

This is valid for the given constraints, but the interval DP version is more useful for learning because it also works for many related game problems where the shortcut does not apply.

Testing

def run_tests():
    s = Solution()

    assert s.stoneGame([5, 3, 4, 5]) is True
    assert s.stoneGame([2, 1]) is True
    assert s.stoneGame([1, 2, 3, 1]) is True
    assert s.stoneGame([7, 8, 8, 10]) is True
    assert s.stoneGame([3, 9, 1, 2]) is True

    print("all tests passed")

run_tests()

Test meaning: