Stone Game III

Difficulty: Hard Source: NeetCode

Problem

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

Alice and Bob take turns, with Alice starting first. On each player’s turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.

Both players play optimally. If Alice wins, return "Alice". If Bob wins, return "Bob". If they tie, return "Tie".

Example 1: Input: stoneValue = [1,2,3,7] Output: "Bob"

Example 2: Input: stoneValue = [1,2,3,-9] Output: "Alice"

Example 3: Input: stoneValue = [1,2,3,6] Output: "Tie"

Constraints:

• 1 <= stoneValue.length <= 5 * 10^4
• -1000 <= stoneValue[i] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Game Theory / Minimax — optimal play for both players
• DP from the End — building solutions right-to-left
• Prefix Sums — quickly computing sums of subarrays

1. Brute Force (Recursion without Memoization)

Intuition

At each position, the current player picks 1, 2, or 3 stones. They want to maximize their own score minus the opponent’s score (from the remaining stones). dp(i) = best score difference (current player minus other player) starting from position i.

Without memoization this is O(3^n) but conceptually clean.

Algorithm

1. dp(i) = best score advantage the current player can achieve from index i to end.
2. For each choice k in {1, 2, 3}: take sum(stoneValue[i:i+k]) and subtract dp(i+k) (opponent’s best from that point).
3. Return max of all choices.

Solution

def stoneGameIII_brute(stoneValue):
    n = len(stoneValue)
    memo = {}

    def dp(i):
        if i >= n:
            return 0
        if i in memo:
            return memo[i]
        best = float('-inf')
        total = 0
        for k in range(1, 4):
            if i + k - 1 < n:
                total += stoneValue[i + k - 1]
                # Current player gains `total`, opponent gets dp(i+k)
                score = total - dp(i + k)
                best = max(best, score)
        memo[i] = best
        return best

    result = dp(0)
    if result > 0:
        return "Alice"
    elif result < 0:
        return "Bob"
    return "Tie"


print(stoneGameIII_brute([1, 2, 3, 7]))   # "Bob"
print(stoneGameIII_brute([1, 2, 3, -9]))  # "Alice"
print(stoneGameIII_brute([1, 2, 3, 6]))   # "Tie"

Complexity

• Time: O(n) with memoization
• Space: O(n) — memo and recursion stack

2. Dynamic Programming (Bottom-Up)

Intuition

Build the DP array right-to-left. dp[i] = best score difference the current player can achieve starting from position i. The current player takes 1, 2, or 3 stones and gains their sum, while the opponent plays optimally from position i+k (giving dp[i+k]).

dp[i] = max(sum(stoneValue[i:i+k]) - dp[i+k] for k in 1,2,3)

At the end, dp[0] is Alice’s score advantage. If positive, Alice wins; negative, Bob wins; zero, tie.

Algorithm

1. Initialize dp = [0] * (n + 3) (padding with zeros for out-of-bounds).
2. Precompute prefix sums for fast range sums.
3. Fill from right to left: dp[i] = max(prefix[i+k] - prefix[i] - dp[i+k] for k in 1,2,3).
4. Return “Alice” if dp[0] > 0, “Bob” if dp[0] < 0, else “Tie”.

Solution

def stoneGameIII(stoneValue):
    n = len(stoneValue)

    # dp[i] = max score advantage (current player - other) from index i
    # We need dp[n], dp[n+1], dp[n+2] to be 0 (base cases)
    dp = [0] * (n + 3)

    # Precompute prefix sums for O(1) range queries
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stoneValue[i]

    def range_sum(l, r):
        """Sum of stoneValue[l:r] (exclusive r)."""
        return prefix[min(r, n)] - prefix[l]

    # Fill right to left
    for i in range(n - 1, -1, -1):
        best = float('-inf')
        for k in range(1, 4):
            if i + k <= n:
                taken = range_sum(i, i + k)
                score = taken - dp[i + k]
                best = max(best, score)
        dp[i] = best

    result = dp[0]
    if result > 0:
        return "Alice"
    elif result < 0:
        return "Bob"
    return "Tie"


print(stoneGameIII([1, 2, 3, 7]))    # "Bob"
print(stoneGameIII([1, 2, 3, -9]))   # "Alice"
print(stoneGameIII([1, 2, 3, 6]))    # "Tie"
print(stoneGameIII([-1, -2, -3]))    # "Tie" (both forced to take; Alice takes first, total sum split)
print(stoneGameIII([7]))             # "Alice"

Complexity

• Time: O(n) — single pass right-to-left, constant work per position
• Space: O(n) — DP array and prefix sums

Common Pitfalls

Modeling dp[i] as the current player’s total score instead of the score difference. Using the score difference (current_player - opponent) elegantly handles the alternating nature of the game without needing to track whose turn it is.

Forgetting negative stone values. Unlike many stone game problems, values here can be negative. A player might be forced to take negative-value stones. The minimax dp handles this correctly since even a negative total - dp[i+k] might be the best available option.

Iterating left-to-right without correct dependencies. dp[i] depends on dp[i+1], dp[i+2], dp[i+3]. You must fill the array from right to left so those values are already computed.