Stone Game VIII — Solution in Python, Java & C++
Stone Game VIII solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Stone Game VIII is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Math, Prefix Sum, Game Theory
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Alice and Bob take turns, Alice first. While more than one stone remains, the player to move chooses an integer x > 1, removes the first x stones, scores their sum, and puts a new stone of that value at the front of the row.
Alice maximises the difference between her score and Bob's; Bob minimises it. Return that difference with both playing optimally.
Example 1
Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation: Alice takes the first four, scoring 2; the row becomes `[2,-5]` and Bob must take both, scoring −3.
Example 2
Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Example 3
Input: stones = [-10,-12]
Output: -22
Explanation: Alice has no choice but to take both stones.
Constraints
n == stones.length2 <= n <= 10^5-10^4 <= stones[i] <= 10^4
Hints for Stone Game VIII
Hint 1
After any move the row is always "a merged stone followed by an untouched suffix", and the merged stone's value is a prefix sum of the original array.
Hint 2
So the whole game is: the mover picks a prefix-sum index
i >= 1, scorespre[i], and the opponent then plays from indexi+1onwards.Hint 3
Sweep
ifrom the end: the best for the mover ismax(best_from_i+1, pre[i] - best_from_i+1).
How to solve Stone Game VIII
Every position is described by a single index: the merged stone is always pre[i] for some prefix i, and the untouched stones are i+1..n-1. A move from state i scores pre[j] for some j > i and hands the opponent state j. Sweeping from the right, best[i] = max(best[i+1], pre[i] - best[i+1]).
Approach
- Build prefix sums
pre. - Initialise
best = pre[n-1]— the last possible move takes everything. - Sweep
ifromn-2down to 1, settingbest = max(best, pre[i] - best). - Return
best, the value of Alice's first move.
Why it works
The collapse to one index is the entire trick. It looks like a game over arbitrary configurations, but merging means the left part is only ever a single number — its prefix sum — so the state is just "how far in". The recurrence then reads as "either skip this prefix and keep the opponent's best, or take it and subtract what the opponent can force", and sweeping right-to-left makes it O(n). The sweep starts at i = 1 because the first move must take at least two stones.
Complexity
- Time —
O(n) - Space —
O(n), or O(1) folding the prefix sum into the sweep
Pitfalls
x > 1, so the first legal prefix is index 1, not 0.- The base case is
pre[n-1]— taking every remaining stone is always available. - The sweep must go right to left; left to right has no correct reading.
Reference solution
Python
from typing import List
def stoneGameVIII(stones: List[int]) -> int:
n = len(stones)
pre = [0] * n
pre[0] = stones[0]
for i in range(1, n):
pre[i] = pre[i - 1] + stones[i]
best = pre[n - 1]
for i in range(n - 2, 0, -1):
best = max(best, pre[i] - best)
return bestJava
public static int stoneGameVIII(int[] stones) {
int n = stones.length;
int[] pre = new int[n];
pre[0] = stones[0];
for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + stones[i];
int best = pre[n - 1];
for (int i = n - 2; i >= 1; i--) best = Math.max(best, pre[i] - best);
return best;
}C++
int stoneGameVIII(vector<int>& stones) {
int n = (int) stones.size();
vector<int> pre(n, 0);
pre[0] = stones[0];
for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + stones[i];
int best = pre[n - 1];
for (int i = n - 2; i >= 1; i--) best = max(best, pre[i] - best);
return best;
}JavaScript
var stoneGameVIII = function(stones) {
var n = stones.length;
var pre = [];
for (var t = 0; t < n; t++) pre.push(0);
pre[0] = stones[0];
for (var i = 1; i < n; i++) pre[i] = pre[i - 1] + stones[i];
var best = pre[n - 1];
for (i = n - 2; i >= 1; i--) {
var take = pre[i] - best;
if (take > best) best = take;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming