LeetCode 1872 - Stone Game VIII

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Prefix Sum, Game Theory

Solution

Problem Understanding

The problem describes a two-player turn-based game between Alice and Bob with a row of stones, each having an integer value. The key rules are that on a turn, a player removes more than one stone from the left, sums their values to their score, and then places a new stone with the summed value on the left. The game continues until only one stone remains.

The input is an integer array stones where stones[i] represents the value of the i-th stone from the left. The output is a single integer representing the score difference (Alice - Bob) if both play optimally. Optimal play means each player aims to maximize their score relative to the other: Alice wants a maximum positive difference, Bob wants a minimum (or negative) difference.

The constraints indicate that n can be as large as 100,000 and values range from -10^4 to 10^4. This suggests that brute-force recursive simulations are infeasible due to the exponential number of move sequences. Important edge cases include arrays of length 2, all positive or negative stones, and arrays with large alternating values which may affect sum choices.

Approaches

A brute-force solution would involve recursively simulating every possible choice of x (number of stones removed) for both players and computing the resulting scores. While this would give a correct answer, the number of possible move sequences grows exponentially with n, making it impractical for large arrays (n up to 10^5).

The key observation for an optimal solution comes from recognizing the prefix sum structure and that the game has a monotone dynamic programming property. We can precompute prefix sums of the stones so that any move sum can be computed in constant time. Moreover, by analyzing the score difference, we can reduce the problem to a maximization problem over suffixes of the prefix sum array, using a dynamic programming array dp[i] that represents the best score difference if the first i stones remain. The recursion then reduces to a simple greedy DP due to the monotonicity: dp[i] = max(prefix[i] - dp[i-1], dp[i-1]).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Simulate all possible moves recursively for Alice and Bob. Exponential in size, impractical.
Optimal	O(n)	O(n)	Compute prefix sums and apply DP over suffixes using monotone property. Linear scan suffices.

Algorithm Walkthrough

Compute prefix sums: For each index i, calculate the sum of the first i+1 stones. This allows any move sum to be queried in constant time.
Initialize DP array: Let dp[i] represent the maximum score difference Alice can achieve when the stones from index i to the end are left. Start from the second-to-last index since the last move is trivial.
Iterate backward: For each index i from n-2 down to 1, update dp[i] as max(dp[i+1], prefix[i] - dp[i+1]). This represents the choice of either taking the current prefix sum and subtracting the opponent's best, or skipping to the next.
Return result: The optimal score difference is stored in dp[1], corresponding to making the first valid move (removing at least two stones).

Why it works: By using prefix sums and a backward DP, each dp[i] maintains the invariant that it represents the maximum achievable score difference from that position. The recurrence ensures we account for optimal opponent response.

Python Solution

from typing import List

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix = [0] * n
        prefix[0] = stones[0]
        for i in range(1, n):
            prefix[i] = prefix[i-1] + stones[i]

        dp = [0] * n
        dp[-1] = prefix[-1]

        for i in range(n-2, 0, -1):
            dp[i] = max(dp[i+1], prefix[i] - dp[i+1])

        return dp[1]

The Python code first calculates prefix sums. It initializes dp[-1] with the sum of all stones, as the last stone’s removal is trivial. The backward DP loop ensures that at each step, we take the maximum between continuing with the next move or taking the current prefix minus the opponent's best, capturing the optimal adversarial strategy. The final result is stored in dp[1] because the first move must remove at least two stones.

Go Solution

func stoneGameVIII(stones []int) int {
    n := len(stones)
    prefix := make([]int, n)
    prefix[0] = stones[0]
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + stones[i]
    }

    dp := make([]int, n)
    dp[n-1] = prefix[n-1]

    for i := n-2; i > 0; i-- {
        if prefix[i]-dp[i+1] > dp[i+1] {
            dp[i] = prefix[i]-dp[i+1]
        } else {
            dp[i] = dp[i+1]
        }
    }

    return dp[1]
}

The Go implementation mirrors Python’s logic with explicit conditional assignment for clarity. Slice initialization is used for both prefix and dp. The backward iteration ensures the monotone DP property is preserved.

Worked Examples

Example 1: stones = [-1,2,-3,4,-5]

Step	Stones	Prefix sums	DP computation	DP array
Initial	[-1,2,-3,4,-5]	[-1,1,-2,2,-3]	dp[4]=prefix[4]=-3	[-,-,-,-,-3]
i=3	[-1,2,-3,4,-5]	2	dp[3]=max(dp[4], prefix[3]-dp[4])=max(-3,2-(-3))=5	[-,-,-,5,-3]
i=2	[-1,2,-3,4,-5]	-2	dp[2]=max(dp[3], -2-5)=max(5,-7)=5	[-,-,5,5,-3]
i=1	[-1,2,-3,4,-5]	1	dp[1]=max(dp[2], 1-5)=max(5,-4)=5	[-,5,5,5,-3]

Result: 5

Example 2: stones = [7,-6,5,10,5,-2,-6]

Step	DP calculation	DP array
Initialize dp[6]=prefix[6]=13		[,,,,,,13]
Backward updates compute dp[1]=13		[_,13,13,13,13,13,13]

Result: 13

Example 3: stones = [-10,-12]

Only one valid move: remove both stones, sum=-22. Result is -22.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Prefix sums computation and backward DP iteration both require linear time.
Space	O(n)	Prefix sums and DP arrays each require O(n) space.

The algorithm is linear in both time and space, making it feasible for n up to 10^5.

Test Cases

# provided examples
assert Solution().stoneGameVIII([-1,2,-3,4,-5]) == 5  # Example 1
assert Solution().stoneGameVIII([7,-6,5,10,5,-2,-6]) == 13  # Example 2
assert Solution().stoneGameVIII([-10,-12]) == -22  # Example 3

# edge cases
assert Solution().stoneGameVIII([1,2]) == 3  # smallest array, positive
assert Solution().stoneGameVIII([-1,-2]) == -3  # smallest array, negative
assert Solution().stoneGameVIII([0,0,0,0]) == 0  # all zeros
assert Solution().stoneGameVIII([10000,-10000]*50000) == 10000  # large input stress test

Test	Why
[-1,2,-3,4,-5]	Example with mixed values and multiple moves
[7,-6,5,10,5,-2,-6]	Example with large positive sum as optimal move
[-10,-12]	Smallest possible input, only one valid move
[1,2]	Smallest positive array
[-1,-2]	Smallest negative array
[0,0,0,0]	All zeros edge case
[10000,-10000]*50000	Large input to test efficiency