Stone Game

Difficulty: Medium Source: NeetCode

Problem

Alice and Bob play a game with piles of stones arranged in a row. They alternate turns, with Alice going first. On each turn, a player takes the entire pile from either end of the row. The player with the most stones at the end wins. Both play optimally. Return true if Alice wins.

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

Example 2: Input: piles = [3, 7, 2, 3] Output: true

Constraints:

• 2 <= piles.length <= 500
• piles.length is even
• 1 <= piles[i] <= 500
• All elements are distinct

Prerequisites

Before attempting this problem, you should be comfortable with:

• Game theory / minimax — reasoning about optimal play for two players
• Interval DP — subproblems defined over subarrays piles[i..j]

1. Observation (Mathematical Proof)

Intuition

Alice always wins when n is even and all values are distinct. Here’s why: colour the piles alternately “even-indexed” and “odd-indexed”. Alice, going first, can always choose to take either all even-indexed piles or all odd-indexed piles. Since the piles have distinct values, one of these two groups has a strictly higher total. Alice picks the better group and forces Bob to take the worse one. So the answer is always True.

Solution

def stoneGame(piles):
    # Alice always wins when n is even and all values distinct
    return True


print(stoneGame([5, 3, 4, 5]))  # True
print(stoneGame([3, 7, 2, 3]))  # True

Complexity

• Time: O(1)
• Space: O(1)

2. DP — Interval DP (General Game Approach)

Intuition

For a general solution (useful for Stone Game variants), use interval DP. Define dp[i][j] as the maximum score difference (current player’s score minus opponent’s score) that the current player can achieve over the subarray piles[i..j]. The current player picks either piles[i] or piles[j], and then the opponent plays optimally on the remaining subarray.

• Take left: piles[i] - dp[i+1][j] (we gain piles[i], then opponent gains dp[i+1][j] over us)
• Take right: piles[j] - dp[i][j-1]

Alice wins if dp[0][n-1] > 0.

Algorithm

1. Create n x n dp table.
2. Base case: dp[i][i] = piles[i] (only one pile, take it).
3. Fill by increasing interval length (length 2, 3, …, n).
4. dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]).
5. Return dp[0][n-1] > 0.

Solution

def stoneGame(piles):
    n = len(piles)
    dp = [[0] * n for _ in range(n)]

    # Base case: single pile
    for i in range(n):
        dp[i][i] = piles[i]

    # Fill for increasing lengths
    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


print(stoneGame([5, 3, 4, 5]))   # True
print(stoneGame([3, 7, 2, 3]))   # True
print(stoneGame([3, 2]))         # True  (Alice picks 3)


# Recursive with memoization version
def stoneGame_memo(piles):
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(i, j):
        if i == j:
            return piles[i]
        return max(piles[i] - dfs(i + 1, j),
                   piles[j] - dfs(i, j - 1))

    return dfs(0, len(piles) - 1) > 0


print(stoneGame_memo([5, 3, 4, 5]))  # True

Complexity

• Time: O(n²)
• Space: O(n²)

Common Pitfalls

Not understanding the score difference formulation. dp[i][j] is the difference (my score minus opponent’s score), not just my score. So when the current player takes piles[i], the opponent then achieves dp[i+1][j] over the current player — hence piles[i] - dp[i+1][j].

Filling the table in wrong order. You must fill by increasing interval length, not row by row. dp[i][j] depends on dp[i+1][j] and dp[i][j-1], so those must be computed first.

Confusing this with Stone Game II. This problem has a fixed take-one-from-either-end rule. Stone Game II has a more complex “take up to 2M piles” rule — don’t mix up their DP formulations.