LeetCode 1690 - Stone Game VII
This problem describes a two player game played on an array of stones. Each stone has a positive integer value, and the
Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Game Theory
Solution
Problem Understanding
This problem describes a two player game played on an array of stones. Each stone has a positive integer value, and the stones are arranged in a row. Alice moves first, and on every turn the current player removes either the leftmost stone or the rightmost stone.
The scoring rule is the key detail that makes this problem interesting. When a player removes a stone, they do not gain the value of the removed stone. Instead, they gain the sum of all remaining stones after the removal.
For example, if the current stones are:
[5, 3, 1, 4]
and the player removes 5, the remaining stones become:
[3, 1, 4]
The player gains:
3 + 1 + 4 = 8
Alice wants to maximize the final score difference:
Alice score - Bob score
Bob wants to minimize that same difference. Since both players play optimally, this is a classic minimax game theory problem.
The input is an integer array stones, where:
stones[i]is the value of thei-thstone2 <= n <= 10001 <= stones[i] <= 1000
The output is a single integer representing the final optimal score difference between Alice and Bob.
The constraint n <= 1000 is extremely important. A naive recursive game simulation would explore exponentially many possibilities, which is far too slow. Since the array size is moderate, this strongly suggests a dynamic programming solution.
An important observation is that the game state is fully determined by the remaining subarray:
stones[left:right]
No additional information is needed because the score gained from a move depends only on the current remaining stones.
Several edge cases are important:
- Arrays with only two stones
- Arrays where all values are identical
- Arrays with very large values
- Situations where greedy removal is incorrect
A naive greedy strategy can fail because taking the immediately larger score may allow the opponent to gain a much larger advantage later.
Approaches
Brute Force Approach
The brute force solution recursively tries every possible move.
At each game state:
- Remove the left stone
- Remove the right stone
- Recursively compute the opponent's best response
- Choose the move that gives the best final score difference
The recursion naturally forms a minimax game tree.
Suppose the current subarray is:
stones[left:right]
If the player removes the left stone:
gain = sum(left+1 ... right)
Then the opponent plays optimally on the smaller subarray.
Similarly, removing the right stone gives:
gain = sum(left ... right-1)
The brute force solution is correct because it exhaustively explores every possible game sequence and assumes optimal play from both sides.
However, the same subproblems are recomputed repeatedly. Since every state branches into two more states, the total complexity becomes exponential.
For n = 1000, this is completely infeasible.
Key Insight
The critical observation is that the game has overlapping subproblems.
The optimal result for a subarray:
stones[left:right]
will be needed many times.
We can define:
dp[left][right]
as the maximum score difference the current player can achieve over the opponent when considering only the subarray:
stones[left:right]
This transforms the problem into interval dynamic programming.
Another important optimization is prefix sums.
Since every move requires computing the sum of remaining stones, repeatedly summing subarrays would be too expensive. Prefix sums allow constant time range sum queries.
The recurrence becomes:
- Remove left stone:
remaining_sum_after_left_removal - opponent_advantage
- Remove right stone:
remaining_sum_after_right_removal - opponent_advantage
We choose the maximum because the current player wants the largest score difference.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Explores every possible game sequence recursively |
| Optimal Dynamic Programming | O(n^2) | O(n^2) | Uses interval DP with prefix sums |
Algorithm Walkthrough
Step 1: Build Prefix Sums
We first construct a prefix sum array so we can compute any subarray sum in constant time.
If:
prefix[i]
stores the sum of the first i elements, then:
sum(left, right) = prefix[right + 1] - prefix[left]
This is essential because every move requires computing the sum of remaining stones.
Step 2: Define the DP State
Define:
dp[left][right]
as the maximum score difference the current player can achieve from the subarray:
stones[left:right+1]
This value already assumes both players play optimally.
Step 3: Handle the Base Case
If:
left == right
there is only one stone remaining.
Removing it leaves no stones, so the player gains 0 points.
Therefore:
dp[left][right] = 0
Step 4: Compute Transition for Removing Left Stone
If the current player removes the leftmost stone:
stones[left]
then the remaining subarray becomes:
[left+1, right]
The player gains:
sum(left+1, right)
But afterward, the opponent can achieve:
dp[left+1][right]
advantage over the current player.
Therefore the net advantage is:
remove_left =
sum(left+1, right) - dp[left+1][right]
Step 5: Compute Transition for Removing Right Stone
Similarly, if the player removes the rightmost stone:
stones[right]
the remaining subarray becomes:
[left, right-1]
The gained score is:
sum(left, right-1)
The opponent then achieves:
dp[left][right-1]
So:
remove_right =
sum(left, right-1) - dp[left][right-1]
Step 6: Choose the Better Move
The current player wants the maximum possible advantage.
So:
dp[left][right] =
max(remove_left, remove_right)
Step 7: Fill the DP Table by Increasing Length
Smaller intervals must be solved before larger intervals.
We iterate over interval lengths from 2 to n.
For every interval:
[left, right]
we compute the DP value using previously solved smaller intervals.
Step 8: Return the Final Answer
The full game corresponds to:
dp[0][n-1]
which represents the optimal score difference Alice can achieve over Bob.
Why it works
The DP recurrence works because every move splits the game into a smaller identical subproblem. After the current player chooses a move, the opponent faces the exact same optimization problem on the remaining interval.
The recurrence correctly models optimal play from both sides:
- The current player maximizes score difference
- The opponent's optimal future advantage is subtracted
- Every possible move is considered
Since all intervals are solved exactly once and built from smaller valid intervals, the final result is correct.
Python Solution
from typing import List
class Solution:
def stoneGameVII(self, stones: List[int]) -> int:
n = len(stones)
# Build prefix sums
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + stones[i]
# dp[left][right] =
# maximum score difference current player can achieve
dp = [[0] * n for _ in range(n)]
# length represents interval size
for length in range(2, n + 1):
for left in range(n - length + 1):
right = left + length - 1
# Sum after removing left stone
remove_left_sum = (
prefix[right + 1] - prefix[left + 1]
)
# Sum after removing right stone
remove_right_sum = (
prefix[right] - prefix[left]
)
remove_left = (
remove_left_sum - dp[left + 1][right]
)
remove_right = (
remove_right_sum - dp[left][right - 1]
)
dp[left][right] = max(
remove_left,
remove_right
)
return dp[0][n - 1]
The implementation begins by building a prefix sum array. This allows constant time range sum queries, which is necessary because every move depends on the sum of remaining stones.
The DP table stores optimal score differences for every interval. Initially all values are zero because intervals of size one produce zero score.
The outer loop iterates over interval lengths from smallest to largest. This ordering is important because larger intervals depend on already solved smaller intervals.
For every interval:
[left, right]
the algorithm evaluates both possible moves:
- Remove the left stone
- Remove the right stone
Each move gains the remaining subarray sum, then subtracts the opponent's optimal response from the resulting interval.
The maximum of the two choices becomes the optimal answer for that interval.
Finally, the answer for the entire array is returned.
Go Solution
func stoneGameVII(stones []int) int {
n := len(stones)
// Build prefix sums
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
prefix[i+1] = prefix[i] + stones[i]
}
// dp[left][right]
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
// Iterate by interval length
for length := 2; length <= n; length++ {
for left := 0; left <= n-length; left++ {
right := left + length - 1
removeLeftSum := prefix[right+1] - prefix[left+1]
removeRightSum := prefix[right] - prefix[left]
removeLeft := removeLeftSum - dp[left+1][right]
removeRight := removeRightSum - dp[left][right-1]
if removeLeft > removeRight {
dp[left][right] = removeLeft
} else {
dp[left][right] = removeRight
}
}
}
return dp[0][n-1]
}
The Go implementation follows the same logic as the Python version.
Go does not provide built in dynamic multidimensional arrays, so the DP table is created manually using nested slices.
Integer overflow is not an issue because the maximum total stone sum is:
1000 * 1000 = 1,000,000
which easily fits inside Go's int type.
Unlike Python, Go does not have a built in max function for integers, so the comparison is implemented with a standard if statement.
Worked Examples
Example 1
Input:
stones = [5,3,1,4,2]
Prefix Sums
| Index | Prefix Sum |
|---|---|
| 0 | 0 |
| 1 | 5 |
| 2 | 8 |
| 3 | 9 |
| 4 | 13 |
| 5 | 15 |
Length = 2
| Interval | removeLeft | removeRight | dp |
|---|---|---|---|
| [5,3] | 3 | 5 | 5 |
| [3,1] | 1 | 3 | 3 |
| [1,4] | 4 | 1 | 4 |
| [4,2] | 2 | 4 | 4 |
Length = 3
| Interval | removeLeft | removeRight | dp |
|---|---|---|---|
| [5,3,1] | 4 - 3 = 1 | 8 - 5 = 3 | 3 |
| [3,1,4] | 5 - 4 = 1 | 4 - 3 = 1 | 1 |
| [1,4,2] | 6 - 4 = 2 | 5 - 4 = 1 | 2 |
Length = 4
| Interval | removeLeft | removeRight | dp |
|---|---|---|---|
| [5,3,1,4] | 8 - 1 = 7 | 9 - 3 = 6 | 7 |
| [3,1,4,2] | 7 - 2 = 5 | 8 - 1 = 7 | 7 |
Length = 5
| Interval | removeLeft | removeRight | dp |
|---|---|---|---|
| [5,3,1,4,2] | 10 - 7 = 3 | 13 - 7 = 6 | 6 |
Final answer:
6
Example 2
Input:
stones = [7,90,5,1,100,10,10,2]
The DP table eventually computes:
dp[0][7] = 122
So the final answer is:
122
A full manual trace would be extremely large because the DP table contains:
8 * 8 = 64
states.
The important observation is that every interval is computed from smaller intervals using the same recurrence relation.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2) | There are O(n^2) intervals, each processed in O(1) time |
| Space | O(n^2) | The DP table stores results for all intervals |
The DP table contains one entry for every possible interval:
n * n
Each entry performs only constant time work because prefix sums allow instant range sum computation.
Therefore the total runtime is quadratic.
Test Cases
sol = Solution()
# Provided example 1
assert sol.stoneGameVII([5, 3, 1, 4, 2]) == 6
# Provided example 2
assert sol.stoneGameVII([7, 90, 5, 1, 100, 10, 10, 2]) == 122
# Minimum valid input size
assert sol.stoneGameVII([1, 2]) == 2
# Equal values
assert sol.stoneGameVII([4, 4, 4, 4]) == 8
# Strictly increasing values
assert sol.stoneGameVII([1, 2, 3, 4, 5]) == 6
# Strictly decreasing values
assert sol.stoneGameVII([5, 4, 3, 2, 1]) == 6
# Large middle value
assert sol.stoneGameVII([1, 100, 1]) == 1
# All ones
assert sol.stoneGameVII([1, 1, 1, 1, 1]) == 2
# Two equal stones
assert sol.stoneGameVII([10, 10]) == 10
# Large values
assert sol.stoneGameVII([1000, 1000, 1000]) == 1000
| Test | Why |
|---|---|
[5,3,1,4,2] |
Validates standard mixed case |
[7,90,5,1,100,10,10,2] |
Larger example with many optimal decisions |
[1,2] |
Smallest possible input |
[4,4,4,4] |
Ensures symmetry is handled correctly |
[1,2,3,4,5] |
Increasing sequence |
[5,4,3,2,1] |
Decreasing sequence |
[1,100,1] |
Tests non greedy optimal play |
[1,1,1,1,1] |
Uniform values |
[10,10] |
Equal two element case |
[1000,1000,1000] |
Large values near constraint limits |
Edge Cases
Minimum Length Array
The smallest valid input contains only two stones.
For example:
[1, 2]
The first player removes one stone and gains the value of the remaining stone. The second player then gains zero because no stones remain afterward.
This case is important because many interval DP implementations accidentally mishandle very small intervals. The implementation handles it naturally because intervals of length 2 are computed directly from base cases of length 1.
All Stones Have Equal Values
Consider:
[4,4,4,4]
Since both removal choices often appear equivalent, it is easy to incorrectly assume greedy behavior works.
However, future interval structure still matters. The DP formulation correctly evaluates both possibilities recursively, ensuring optimal play even when values are identical.
Greedy Choices Can Fail
Consider:
[1,100,1]
A greedy strategy that maximizes immediate gain may not maximize the final score difference.
The algorithm avoids this mistake by accounting for the opponent's optimal response:
current_gain - opponent_best_result
This is the essential minimax principle that guarantees correctness.
Large Input Size
The maximum input size is:
n = 1000
An exponential recursive solution would be impossible to run within time limits.
The interval DP solution computes each state once, resulting in manageable quadratic complexity.