Stone Game VI

Medium
1481.

Stone Game VI

Stone Game VI is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 10^5
  • 1 <= aliceValues[i], bobValues[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} aliceValues
 * @param {number[]} bobValues
 * @return {number}
 */
var stoneGameVI = function(aliceValues, bobValues) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 10^5
  • 1 <= aliceValues[i], bobValues[i] <= 100

Hints for Stone Game VI

  1. Hint 1

    Taking a stone does two things: you gain your value and your opponent loses theirs.

  2. Hint 2

    So stone i is worth aliceValues[i] + bobValues[i] to whoever takes it, in terms of the score difference.

  3. 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

  1. Compute s[i] = aliceValues[i] + bobValues[i] and sort descending.
  2. Alice gets the stones at even positions of that order (0, 2, 4, …), Bob the rest.
  3. The difference is Σ s at even positions − Σ bobValues.
  4. 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 + b can 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