#1686

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Stone Game VI

Determine the winner in Stone Game VI using a greedy strategy that accounts for each stone's dual value impact on Alice and Bob.

array math greedy sorting heap priority queue

Problem Statement

Alice and Bob play a game with n stones arranged in a pile. Each stone has a value for Alice and a possibly different value for Bob. The players take turns removing one stone from the pile, starting with Alice, and add its value to their total score. The player with the higher total score at the end wins, or the game ends in a draw if scores are equal.

You are given two integer arrays, aliceValues and bobValues, each of length n. For each stone i, aliceValues[i] is the value Alice receives if she takes it, and bobValues[i] is the value Bob receives if he takes it. Compute the result of the game assuming both players play optimally: return 1 if Alice wins, -1 if Bob wins, and 0 if the game ends in a draw.

Examples

Example 1

Input: aliceValues = [1,3], bobValues = [2,1]

Output: 1

If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points. Bob can only choose stone 0, and will only receive 2 points. Alice wins.

Example 2

Input: aliceValues = [1,2], bobValues = [3,1]

Output: 0

If Alice takes stone 0, and Bob takes stone 1, they will both have 1 point. Draw.

Example 3

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

Output: -1

Regardless of how Alice plays, Bob will be able to have more points than Alice. For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7. Bob wins.

Constraints

n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100

Solution Approach

Compute stone impact for greedy selection

Calculate a combined value for each stone as aliceValues[i] + bobValues[i]. This represents the total points that the stone influences. Sorting stones in descending order of this combined value allows each player to maximize personal gain while limiting the opponent's score.

Simulate turn-based selection

Iterate over the sorted stones, alternately assigning points to Alice and Bob. On Alice's turn, add aliceValues[i] to her score; on Bob's turn, add bobValues[i] to his score. This greedy simulation ensures that the invariant of maximizing net impact per move is maintained.

Determine winner

After all stones are taken, compare total scores. Return 1 if Alice's total exceeds Bob's, -1 if Bob's total exceeds Alice's, or 0 if totals are equal. This final evaluation captures the result of optimal greedy play for Stone Game VI.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting the stones by combined value. Space complexity is O(n) for storing the combined values and scores. The greedy selection avoids more complex DP solutions, exploiting the invariant that the highest combined value stone is always the optimal next choice.

What Interviewers Usually Probe

Ask why sorting by combined value works instead of sorting by individual player values.
Probe understanding of why each turn affects both players' potential scores.
Check if the candidate considers edge cases like draws or stones with equal combined value.

Common Pitfalls or Variants

Common pitfalls

Sorting by only Alice's or Bob's value can mislead the greedy choice.
Failing to alternate turns correctly can invert expected score advantage.
Ignoring the opponent's potential points from each stone leads to wrong winner calculation.

Follow-up variants

Game with three players, requiring tracking cumulative impact across all three scores.
Stones with negative values, adding risk management to greedy selection.
Allowing removal of multiple stones per turn, changing the invariant for optimal selection.

FAQ

What is the main strategy to solve Stone Game VI efficiently?

The main strategy is a greedy approach where each stone is evaluated by the sum of Alice's and Bob's values. Sorting by this sum and taking turns ensures optimal play.

Why do we sort stones by combined value instead of individual player value?

Sorting by combined value ensures that each move maximizes total impact: a high-value stone for both players limits the opponent while increasing your own score.

Can Stone Game VI result in a draw?

Yes, if both players end up with equal total points after all stones are taken, the game results in a draw.

What is the time complexity of the greedy solution for Stone Game VI?

The solution runs in O(n log n) time due to sorting, with O(n) space to track combined values and scores.

How does the greedy choice plus invariant validation pattern apply here?

Each stone selection is made to maximize net advantage while maintaining the invariant that the next chosen stone has the highest combined impact, ensuring optimal point accumulation.

terminal

Solution

Solution 1: Greedy + Sorting

The optimal strategy for picking stones is to maximize one's own score while making the opponent lose as much as possible. Therefore, we create an array $vals$, where $vals[i] = (aliceValues[i] + bobValues[i], i)$ represents the total value and index of the $i$-th stone. Then we sort $vals$ in descending order by total value.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        vals = [(a + b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))]
        vals.sort(reverse=True)
        a = sum(aliceValues[i] for _, i in vals[::2])
        b = sum(bobValues[i] for _, i in vals[1::2])
        if a > b:
            return 1
        if a < b:
            return -1
        return 0

Continue Practicing

#1648 sell diminishing valued colored balls #1561 maximum number of coins you can get #1878 get biggest three rhombus sums in a grid