358. Stone Game VI

Taking stone i does two things: it gains you your value, AND it denies the opponent their value. The true priority of a stone is aliceValues[i] + bobValues[i]. Sort stones by that sum, descending; players alternate picking from the top, Alice first.

The key exchange argument

When it is your turn, picking stone i is worth more than just your own points. You also stop the opponent from ever scoring their bobValues[i] (or aliceValues[i]) on it. So the real contested worth of a stone is:

priority(i) = aliceValues[i] + bobValues[i]

Suppose two stones x and y are up for grabs and priority(x) > priority(y). A short exchange argument shows every optimal strategy prefers the higher-priority stone first: swapping to take the lower one can never improve your margin. Therefore both players, on their turn, greedily grab the remaining stone with the largest combined value.

Algorithm

1. Sort the stone indices by aliceValues[i] + bobValues[i] in descending order.
2. Walk the sorted list. Alice takes positions 0, 2, 4, ... (adding her aliceValues), Bob takes positions 1, 3, 5, ... (adding his bobValues).
3. Compare totals: +1 if Alice leads, -1 if Bob leads, 0 if tied.

Worked example

aliceValues = [1, 3], bobValues = [2, 1].

Combined values: stone 0 → 1+2 = 3, stone 1 → 3+1 = 4.

Sorted descending by combined value: [stone 1 (4), stone 0 (3)].

• Turn 0 (Alice): takes stone 1 → Alice += aliceValues[1] = 3.
• Turn 1 (Bob): takes stone 0 → Bob += bobValues[0] = 2.

Alice 3, Bob 2 → Alice wins → return 1.

Complexity

• Time: O(n log n) — dominated by the sort.
• Space: O(n) for the index order.

class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        // A stone's contested worth is (my gain) + (opponent's denied gain).
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) ->
            (aliceValues[b] + bobValues[b]) - (aliceValues[a] + bobValues[a]));
        long alice = 0, bob = 0;
        for (int turn = 0; turn < n; turn++) {
            int idx = order[turn];
            if (turn % 2 == 0) alice += aliceValues[idx];
            else bob += bobValues[idx];
        }
        return Long.compare(alice, bob);
    }
}