Stone Game VI: Greedy Selection by Combined Value

Alice and Bob take turns picking stones from a pile, with Alice going first. Each stone has a different value for each player: aliceValues[i] is how much stone i is worth to Alice, and bobValues[i] is how much it is worth to Bob. Both players play optimally to maximize their own score. Return 1 if Alice wins, -1 if Bob wins, or 0 if the game is a tie.

This is LeetCode 1686: Stone Game VI, a medium problem that looks like it needs game tree search or dynamic programming but actually has a clean greedy solution. The trick is realizing that each player should pick stones based on the combined value, not just their own.

The problem

You are given two integer arrays aliceValues and bobValues, both of length n. Alice and Bob alternate turns, with Alice picking first. On each turn, a player picks any remaining stone and adds their value for that stone to their score. After all stones are picked, compare the scores: return 1 if Alice has more, -1 if Bob has more, and 0 if they are tied.

Consider aliceValues = [1,3] and bobValues = [2,1]. The combined values are [3,4]. Stone 1 has a combined value of 4, which is the highest. Alice picks stone 1 first (gaining 3 points) and Bob picks stone 0 (gaining 2 points). Alice wins 3 to 2. If Alice had naively picked the stone with the highest Alice value (stone 1, value 3), she would still win here, but that greedy strategy fails on other inputs. The combined value approach always works.

The brute force approach

You could try all possible orderings of stone picks. With n stones, there are n! permutations to consider. For each permutation, simulate the game where Alice picks stones at even positions and Bob picks stones at odd positions, then compare scores. This gives an O(n!) time solution, which is completely impractical for n up to 10^5.

from itertools import permutations

def stoneGameVI_brute(aliceValues, bobValues):
    n = len(aliceValues)
    best = -2
    for perm in permutations(range(n)):
        alice = sum(aliceValues[perm[i]] for i in range(0, n, 2))
        bob = sum(bobValues[perm[i]] for i in range(1, n, 2))
        diff = alice - bob
        if diff > best:
            best = diff
    if best > 0:
        return 1
    elif best < 0:
        return -1
    return 0

This explores far too many possibilities. We need a way to determine the optimal pick order without trying them all.

The key insight

When Alice picks stone i, two things happen simultaneously: Alice gains aliceValues[i] points, and Bob loses the opportunity to score bobValues[i] from that stone. The total impact of Alice picking stone i is aliceValues[i] + bobValues[i]. It is the same from Bob's perspective: picking stone i gives Bob bobValues[i] and denies Alice aliceValues[i], for a total swing of aliceValues[i] + bobValues[i].

This means both players should prioritize stones with the highest combined value, regardless of which individual value is higher. A stone worth 1 to Alice and 10 to Bob has a combined value of 11, and Alice should seriously consider picking it, not because she gains much, but because she denies Bob a huge score.

Step-by-step walkthrough

Let's trace through a larger example: aliceValues = [1,2,3,7], bobValues = [6,2,3,1]. The combined values are [7,4,6,8].

Sorting by combined value and alternating picks gives Alice a score of 10 and Bob a score of 8. Alice wins, so we return 1.

The code

def stoneGameVI(aliceValues, bobValues):
    n = len(aliceValues)
    indices = sorted(range(n), key=lambda i: aliceValues[i] + bobValues[i], reverse=True)
    alice_score = sum(aliceValues[i] for i in indices[::2])
    bob_score = sum(bobValues[i] for i in indices[1::2])
    if alice_score > bob_score:
        return 1
    elif alice_score < bob_score:
        return -1
    return 0

Here is what each piece does:

1. Sort indices by combined value. We create a list of indices [0, 1, ..., n-1] and sort them in descending order of aliceValues[i] + bobValues[i]. This gives us the optimal picking order.
2. Alice picks stones at even positions. Since Alice goes first, she picks the stones at indices 0, 2, 4, ... in the sorted order. Her score is the sum of her values for those stones.
3. Bob picks stones at odd positions. Bob picks the stones at indices 1, 3, 5, ... in the sorted order. His score is the sum of his values for those stones.
4. Compare and return. If Alice's total is higher, return 1. If Bob's is higher, return -1. Otherwise, return 0.

Complexity analysis

The greedy solution is dominated by the sort, which takes O(n log n). The subsequent summation passes are O(n). The space is O(n) for the sorted index array.

The building blocks

Greedy by opportunity cost

The core idea here is that picking a stone is not just about how much you gain. It is about the total swing: your gain plus the opponent's loss. This "opportunity cost" framing turns a two-player game into a single sorting problem.

This pattern appears whenever two players compete for shared resources. Instead of modeling the game tree, you can often reduce the problem to a greedy sort by the combined benefit. The key condition is that both players should agree on the priority order, which happens when the combined value captures the full strategic impact of each choice.

Sorting indices by derived key

Rather than sorting the values arrays directly, we sort an array of indices by a derived key (aliceValues[i] + bobValues[i]). This lets us preserve the mapping between indices and both value arrays while still ordering by the criterion we care about. This is a common technique when you need to sort by one criterion but read values from multiple arrays using the original indices.

indices = sorted(range(n), key=lambda i: some_function(i), reverse=True)

This pattern shows up in many problems where you need to process elements in a specific order but still need access to their original positions or related data.

Edge cases

Before submitting, make sure your solution handles these:

• Single stone aliceValues = [5], bobValues = [3]: Alice picks the only stone, scores 5. Bob scores 0. Return 1.
• All values equal aliceValues = [2,2], bobValues = [2,2]: combined values are all 4. Alice picks one stone (2 points), Bob picks the other (2 points). Tie, return 0.
• One player has all zeros aliceValues = [0,0,0], bobValues = [3,2,1]: combined values are [3,2,1]. Alice picks in order of highest combined value, but her values are all 0. She scores 0 while Bob scores whatever he picks. Bob wins.
• Large combined value with low self-value: if aliceValues[i] = 1 and bobValues[i] = 100, the combined value is 101. Alice should still pick this stone first because denying Bob 100 points far outweighs the low personal gain.

From understanding to recall

The entire solution hinges on one insight: the value of picking a stone is aliceValues[i] + bobValues[i], because you gain your value and deny the opponent theirs. Once you internalize that the "greedy key" is the combined value, the code is a sort followed by a split into alternating picks.

The pattern to remember is "gain plus denial equals priority." Any time two players compete for shared items with different valuations, sorting by the sum of both valuations gives the optimal greedy order. Practice writing the three-line core (sort indices, sum even positions, sum odd positions) until it is automatic.

Related posts

• Assign Cookies - Another greedy assignment problem where sorting by the right criterion is key.
• Advantage Shuffle - Greedy pairing where you must consider both your gain and opponent's values.
• Best Time to Buy and Sell Stock - Greedy optimization that finds the single best decision at each step.