Problem Description

Alice and Bob are playing a stone-picking game where they take turns choosing stones from a pile, with Alice going first.

The game setup:

• There are n stones in a pile
• Each stone has different values for Alice and Bob
• aliceValues[i] represents how much Alice values the i-th stone
• bobValues[i] represents how much Bob values the i-th stone
• When a player picks a stone, they receive points equal to their own valuation of that stone

The game rules:

• Players alternate turns (Alice first, then Bob, then Alice, etc.)
• On each turn, a player removes one stone from the pile and gains points
• Both players play optimally (making the best possible moves)
• Both players know each other's stone valuations

The goal is to determine who wins:

• Return 1 if Alice wins (has more total points)
• Return -1 if Bob wins (has more total points)
• Return 0 if it's a draw (equal points)

The key insight is that when playing optimally, each player should consider not just their own gain from picking a stone, but also what they're denying their opponent. A stone with combined value aliceValues[i] + bobValues[i] represents the total impact of picking that stone - the player gains their value while preventing the opponent from getting their value. Therefore, the optimal strategy is to pick stones in descending order of their combined values, with Alice taking stones at even positions (0, 2, 4, ...) and Bob taking stones at odd positions (1, 3, 5, ...) in this sorted order.

Intuition

When playing optimally, each player needs to think about two things: maximizing their own score and minimizing their opponent's potential score. This is the key to understanding the solution.

Let's think about what happens when Alice picks a stone. She gains aliceValues[i] points, but equally important, she prevents Bob from potentially getting bobValues[i] points if he had picked that stone instead. The total impact of Alice picking stone i is essentially aliceValues[i] + bobValues[i] - she gains her value and denies Bob his value.

Consider a simple example: Suppose there are two stones left:

• Stone A: Alice values it at 3, Bob values it at 1
• Stone B: Alice values it at 2, Bob values it at 5

If Alice picks Stone A, the net effect is +3 for Alice (she gains 3) and Bob loses the opportunity to gain 1. If Alice picks Stone B, the net effect is +2 for Alice but Bob loses the opportunity to gain 5. Even though Alice gets less direct value from Stone B, picking it has a bigger overall impact because it denies Bob more points.

This leads us to the greedy strategy: stones should be picked in order of their combined value aliceValues[i] + bobValues[i]. The stone with the highest combined value has the biggest total impact on the game, regardless of who picks it. Since both players play optimally, they will follow this same strategy.

Therefore, we can simulate the optimal game by:

1. Sorting all stones by their combined value in descending order
2. Having Alice pick the 1st, 3rd, 5th... stones (even indices)
3. Having Bob pick the 2nd, 4th, 6th... stones (odd indices)
4. Calculating final scores and determining the winner

Learn more about Greedy, Math, Sorting and Heap (Priority Queue) patterns.

Solution Approach

Based on our intuition that stones should be picked by their combined value, we implement the greedy solution as follows:

Step 1: Create value-index pairs

vals = [(a + b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))]

We create a list vals where each element is a tuple (combined_value, index). The combined value is aliceValues[i] + bobValues[i], representing the total impact of picking stone i. We keep track of the original index so we know which stone we're referring to after sorting.

Step 2: Sort by combined value

vals.sort(reverse=True)

We sort vals in descending order by the combined value. This ensures that stones with the highest total impact are picked first, which is the optimal strategy for both players.

Step 3: Simulate optimal play

a = sum(aliceValues[i] for _, i in vals[::2])
b = sum(bobValues[i] for _, i in vals[1::2])

• Alice picks stones at even positions in the sorted list: vals[0], vals[2], vals[4], ... (using slice notation vals[::2])
• Bob picks stones at odd positions: vals[1], vals[3], vals[5], ... (using slice notation vals[1::2])
• For each picked stone, we add the respective player's valuation to their score

Step 4: Determine the winner

if a > b:
    return 1
if a < b:
    return -1
return 0

We compare the final scores and return the appropriate result based on who has more points.

Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) for storing the vals array

The key insight is that by sorting stones by their combined value and alternating picks, we simulate the optimal strategy where each player maximizes their gain while denying the opponent the most valuable remaining opportunities.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• aliceValues = [2, 4, 3]
• bobValues = [1, 6, 7]

Step 1: Create value-index pairs

We calculate the combined value for each stone and pair it with its index:

• Stone 0: combined value = 2 + 1 = 3, pair = (3, 0)
• Stone 1: combined value = 4 + 6 = 10, pair = (10, 1)
• Stone 2: combined value = 3 + 7 = 10, pair = (10, 2)

So vals = [(3, 0), (10, 1), (10, 2)]

Step 2: Sort by combined value (descending)

After sorting: vals = [(10, 1), (10, 2), (3, 0)]

This tells us the optimal picking order is: stone 1, then stone 2, then stone 0.

Step 3: Simulate optimal play

Players alternate picking stones from the sorted list:

• Turn 1 (Alice): Picks stone at index 1 (first in sorted list)

  • Alice gains: aliceValues[1] = 4 points

• Turn 2 (Bob): Picks stone at index 2 (second in sorted list)

  • Bob gains: bobValues[2] = 7 points

• Turn 3 (Alice): Picks stone at index 0 (third in sorted list)

  • Alice gains: aliceValues[0] = 2 points

Step 4: Calculate final scores

• Alice's total: 4 + 2 = 6 points
• Bob's total: 7 points

Since Bob has more points (7 > 6), the function returns -1.

Why this strategy works: Notice that both stones 1 and 2 had the same combined value of 10. Alice picked stone 1 first because she goes first. Even though she only got 4 points while Bob got 7 points from stone 2, this was still optimal play. If Alice had picked stone 2 instead (getting 3 points), Bob would have then picked stone 1 (getting 6 points), and Alice would end up with stone 0 (2 points), giving her only 3 + 2 = 5 total points - worse than the 6 points she got with optimal play.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation. Breaking down the algorithm:

• Creating the vals list with combined values takes O(n) time, where we iterate through both arrays once using enumerate and zip
• Sorting the vals list takes O(n × log n) time using Python's Timsort algorithm
• Computing the sum for Alice's values using list slicing vals[::2] takes O(n/2) = O(n) time
• Computing the sum for Bob's values using list slicing vals[1::2] takes O(n/2) = O(n) time
• The final comparisons take O(1) time

Overall: O(n) + O(n × log n) + O(n) + O(n) + O(1) = O(n × log n)

Space Complexity: O(n)

The space complexity analysis:

• The vals list stores n tuples, each containing a sum and an index, requiring O(n) space
• The list slicing operations vals[::2] and vals[1::2] create temporary lists for the generator expressions in the sum functions, but these are evaluated lazily and don't create full lists in memory
• The variables a and b use O(1) space

Overall: O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Sorting by Individual Values Instead of Combined Values

The Mistake: A common misconception is to have each player greedily pick stones based solely on their own valuations:

# INCORRECT approach
alice_stones = sorted(enumerate(aliceValues), key=lambda x: x[1], reverse=True)
bob_stones = sorted(enumerate(bobValues), key=lambda x: x[1], reverse=True)

This fails because it ignores the defensive aspect of the game - preventing your opponent from getting high-value stones.

Example where this fails:

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

If Alice picks based only on her values, she'd choose stone 1 (value 2). Bob then gets stone 0 (value 3).

• Alice's score: 2
• Bob's score: 3
• Result: Bob wins

But if Alice considers combined values:

• Stone 0: combined value = 1 + 3 = 4
• Stone 1: combined value = 2 + 1 = 3

Alice picks stone 0 first (gets 1 point), Bob picks stone 1 (gets 1 point).

• Result: Tie

The Fix: Always sort by combined values aliceValues[i] + bobValues[i] to account for both offensive gain and defensive denial.

Pitfall 2: Incorrect Turn Assignment After Sorting

The Mistake: After sorting by combined values, accidentally assigning the wrong stones to each player:

# INCORRECT - swapping who gets even/odd indices
alice_score = sum(aliceValues[i] for _, i in combined_values[1::2])  # Wrong!
bob_score = sum(bobValues[i] for _, i in combined_values[::2])      # Wrong!

Since Alice goes first, she must get stones at even indices (0, 2, 4, ...) in the sorted list.

The Fix: Remember that Alice always goes first:

• Alice: combined_values[::2] (indices 0, 2, 4, ...)
• Bob: combined_values[1::2] (indices 1, 3, 5, ...)

Pitfall 3: Using Wrong Values When Calculating Scores

The Mistake: Using the combined values for scoring instead of individual player values:

# INCORRECT - using combined value for scoring
alice_score = sum(combined_val for combined_val, _ in combined_values[::2])

The combined value is only for determining pick order. When calculating scores, use each player's individual valuation of the stones they picked.

The Fix: After determining which stones each player picks, use the original value arrays:

alice_score = sum(aliceValues[index] for _, index in combined_values[::2])
bob_score = sum(bobValues[index] for _, index in combined_values[1::2])

Pitfall 4: Not Handling Edge Cases

The Mistake: Not considering edge cases like single stone or empty arrays:

# May fail with index errors on edge cases
if len(aliceValues) == 0:
    # Not handled

The Fix: The provided solution naturally handles these cases:

• Single stone: Alice takes it, Bob gets nothing
• Empty array: Both get 0 points (returns 0)

The slicing operations [::2] and [1::2] handle these gracefully without additional checks.