Watch 6 video solutions for Stone Game VI, a medium level problem involving Array, Math, Greedy. This walkthrough by Aryan Mittal has 4,096 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice and Bob take turns playing a game, with Alice starting first.
There are n stones in a pile. On each player's turn, they can remove a stone from the pile and receive points based on the stone's value. Alice and Bob may value the stones differently.
You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the ith stone.
The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally. Both players know the other's values.
Determine the result of the game, and:
1.-1.0.
Example 1:
Input: aliceValues = [1,3], bobValues = [2,1] Output: 1 Explanation: 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 Explanation: 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 Explanation: 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.length1 <= n <= 1051 <= aliceValues[i], bobValues[i] <= 100Problem Overview: You are given two arrays where aliceValues[i] and bobValues[i] represent how much each player values the same stone. Alice and Bob take turns picking stones. Each player adds the value of the stone from their own array to their score. Both players play optimally, so the task is to determine who wins or if the game ends in a draw.
Approach 1: Maximize Combined Value Strategy (O(n log n) time, O(n) space)
The key insight is that each stone affects both players' outcomes. If Alice takes a stone with high aliceValues[i], she gains points while also preventing Bob from gaining bobValues[i]. Because of this dual impact, prioritize stones with the largest combined value aliceValues[i] + bobValues[i]. Create pairs of indices and sort them in descending order based on this sum using sorting. Then simulate the game turn by turn: Alice picks on even turns, Bob on odd turns. Alice adds aliceValues[i] to her score, Bob adds bobValues[i]. After all stones are taken, compare the final scores to decide the winner.
This works because the combined value measures the total swing a stone creates in the game. A stone with a large sum either gives the current player a big gain or denies the opponent a large future gain. Sorting by this metric ensures the most impactful stones are chosen first.
Approach 2: Greedy Selection Based on Maximum Benefit with Heap (O(n log n) time, O(n) space)
Instead of sorting upfront, maintain a max heap (priority queue) where the priority is the combined value aliceValues[i] + bobValues[i]. Insert all stones into the heap and repeatedly extract the maximum. This naturally gives the next most valuable stone to consider. Alternate turns between players while updating scores accordingly. Using a heap highlights the greedy nature of the decision process and is useful if stones were dynamically added or removed during gameplay.
The heap approach uses a priority queue to always access the best candidate stone in O(log n) time. The overall complexity remains O(n log n) because each insertion and removal costs logarithmic time.
Both strategies rely on greedy reasoning and competitive scoring, a common pattern in game theory problems where players try to maximize advantage while minimizing the opponent’s future options.
Recommended for interviews: The sorting-based greedy solution is the standard answer interviewers expect. It is simple to implement and clearly demonstrates the core insight: evaluate each stone by the combined impact on both players. The heap version shows the same idea using a different data structure but usually adds unnecessary complexity unless the problem constraints require dynamic selection.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Maximize Combined Value Strategy (Sorting) | O(n log n) | O(n) | Best general solution; simple greedy logic and commonly expected in interviews |
| Greedy Selection with Max Heap | O(n log n) | O(n) | Useful when stones must be selected dynamically or when demonstrating priority queue usage |