How to Solve Stone Game VI

Stone Game VI requires selecting stones to maximize personal points while minimizing the opponent's potential. The key is to sort stones by the combined value Alice and Bob assign and greedily pick the highest-impact stones. Each move affects both scores, so tracking cumulative advantage is essential to determine the winner efficiently.

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

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.

How GhostInterview Helps

• Automatically computes optimal greedy selection and alternates turns, preventing manual simulation errors.
• Highlights the stones with maximum combined impact, guiding correct invariant-based choices.
• Generates result evaluation directly, ensuring the winner is determined without miscalculating net gains.

Topic Pages

• Array
• Math
• Greedy
• Sorting
• Heap (Priority Queue)
• Game Theory

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.