Stone Game VI — Solution in Python, Java & C++
Stone Game VI solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and sorting.
Stone Game VI is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Game Theory
- Asked at: Amazon, Google
- 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
There are n stones. Alice and Bob take turns, Alice first; on a turn a player removes any one remaining stone. Stone i is worth aliceValues[i] points to Alice and bobValues[i] points to Bob — each player only scores their own value for the stones they take.
When no stones remain, the player with more points wins. Both players know both arrays and play optimally.
Return 1 if Alice wins, -1 if Bob wins, and 0 for a draw.
Example 1
Input: aliceValues = [1,3], bobValues = [2,1]
Output: 1
Explanation: Alice takes stone 1 (3 points); Bob is left with stone 0 (2 points).
Example 2
Input: aliceValues = [1,2], bobValues = [3,1]
Output: 0
Explanation: Alice takes stone 0 to deny Bob 3 points; both end with 1.
Example 3
Input: aliceValues = [5,1], bobValues = [2,6]
Output: -1
Constraints
n == aliceValues.length == bobValues.length1 <= n <= 10^51 <= aliceValues[i], bobValues[i] <= 100
Hints for Stone Game VI
Hint 1
Taking a stone does two things: you gain your value and your opponent loses theirs.
Hint 2
So stone
iis worthaliceValues[i] + bobValues[i]to whoever takes it, in terms of the score difference.Hint 3
Sort stones by that sum, largest first, and let the players alternate taking them; compare the totals.
How to solve Stone Game VI
Measure everything as Alice's score minus Bob's. Write S = Σ bobValues. If Alice ends with the set A, the difference is Σ_{i∈A} aliceValues[i] − Σ_{i∉A} bobValues[i] = Σ_{i∈A} (aliceValues[i] + bobValues[i]) − S. So both players only care about the combined value a + b of each stone.
Approach
- Compute
s[i] = aliceValues[i] + bobValues[i]and sort descending. - Alice gets the stones at even positions of that order (0, 2, 4, …), Bob the rest.
- The difference is
Σ s at even positions − Σ bobValues. - Return 1, -1 or 0 by its sign.
Why it works
By the identity above, Alice wants to maximise the sum of s over her stones and Bob — by the symmetric identity — wants to maximise it over his. With a common weight for each stone, the best move for either player at every turn is to take the heaviest remaining stone (an exchange argument: swapping a lighter pick for the heaviest one never hurts the picker). Stones with equal s are interchangeable, so ties do not matter.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting by your own value alone is wrong — example 2 shows that denying Bob matters.
- Ties in
a + bcan be broken arbitrarily; the result is the same. - The game is a draw when the difference is exactly 0.
Reference solution
Python
from typing import List
def stoneGameVI(aliceValues: List[int], bobValues: List[int]) -> int:
sums = sorted((a + b for a, b in zip(aliceValues, bobValues)), reverse=True)
diff = sum(sums[0::2]) - sum(bobValues)
return (diff > 0) - (diff < 0)Java
public static int stoneGameVI(int[] aliceValues, int[] bobValues) {
int n = aliceValues.length;
int[] sums = new int[n];
long diff = 0;
for (int i = 0; i < n; i++) {
sums[i] = aliceValues[i] + bobValues[i];
diff -= bobValues[i];
}
Arrays.sort(sums);
for (int t = 0; t < n; t += 2) diff += sums[n - 1 - t];
return diff > 0 ? 1 : diff < 0 ? -1 : 0;
}C++
int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
int n = aliceValues.size();
vector<int> sums(n);
long long diff = 0;
for (int i = 0; i < n; i++) {
sums[i] = aliceValues[i] + bobValues[i];
diff -= bobValues[i];
}
sort(sums.rbegin(), sums.rend());
for (int i = 0; i < n; i += 2) diff += sums[i];
return diff > 0 ? 1 : diff < 0 ? -1 : 0;
}JavaScript
var stoneGameVI = function(aliceValues, bobValues) {
var n = aliceValues.length;
var sums = [];
var diff = 0;
for (var i = 0; i < n; i++) {
sums.push(aliceValues[i] + bobValues[i]);
diff -= bobValues[i];
}
sums.sort(function(x, y) { return y - x; });
for (i = 0; i < n; i += 2) diff += sums[i];
return diff > 0 ? 1 : diff < 0 ? -1 : 0;
};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 · Sorting Algorithms