1686. Stone Game VI

Array
Math
Greedy
Sorting
Heap (Priority Queue)
Game Theory

TIME

O(n log n)

SPACE

O(n)

Intuition

Taking a stone does two things at once: it gains you your own value for it, and it denies the opponent theirs. So the real importance of stone i the swing in the final score difference, is aliceValues[i] + bobValues[i], not either value alone.

That's why a stone can be worth grabbing even if you value it lowly: if the opponent values it highly, taking it is a defensive move. Example 3 shows this, Bob's high values on stones 1 and 2 dominate.

Once every stone is ranked by that combined weight, the game is a simple alternating pick: on each turn the current player should take the highest remaining swing. (An exchange argument confirms it: if a player ever skips the top-swing stone, swapping their pick to that stone never hurts them.)

Approach

Sort the stone indices by aliceValues[i] + bobValues[i] descending.
Alice takes positions 0, 2, 4, ... in that order; Bob takes 1, 3, 5, ....
Sum Alice's own values over her picks and Bob's own values over his.
Compare: 1 if Alice's total is larger, -1 if Bob's is, 0 if equal.

Complexity

Time: O(n log n), dominated by the sort
Space: O(n), the index ordering

Edge Cases

Single stone → Alice takes it; she wins unless her value is 0 (values are ≥ 1, so she always wins)
Ties in a[i] + b[i] → any consistent order gives the same result
A stone Alice values little but Bob values highly may still be her best pick (Example 3's logic)
Totals reach at most 10^5 * 100 = 10^7, comfortably within int
Verified against a full bitmask minimax for n <= 8

Code

from typing import List


class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        """
        1686. Stone Game VI
        Time: O(n log n)
        Space: O(n)
        """
        n = len(aliceValues)
        # A stone's importance is the swing it causes: own gain + opponent's denial.
        order = sorted(range(n), key=lambda i: -(aliceValues[i] + bobValues[i]))

        alice = sum(aliceValues[order[i]] for i in range(0, n, 2))
        bob = sum(bobValues[order[i]] for i in range(1, n, 2))

        if alice > bob:
            return 1
        if alice < bob:
            return -1
        return 0

import java.util.Arrays;

/**
 * 1686. Stone Game VI
 * Time: O(n log n)
 * Space: O(n)
 */
class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;

        // A stone's importance is the swing it causes: own gain + opponent's denial.
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, (x, y) ->
            (bobValues[y] + aliceValues[y]) - (bobValues[x] + aliceValues[x]));

        long alice = 0, bob = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                alice += aliceValues[order[i]];
            } else {
                bob += bobValues[order[i]];
            }
        }

        return Long.compare(alice, bob);
    }
}