Skip to main content
Talentd

Stone Game VI - Solution & Explanation

MediumArrayMathGreedySorting14 min read
Practice this problem

Problem Statement

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:

  • If Alice wins, return 1.
  • If Bob wins, return -1.
  • If the game results in a draw, return 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.length
  • 1 <= n <= 105
  • 1 <= aliceValues[i], bobValues[i] <= 100

Approach Overview

Problem 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 1: Maximize Combined Value Strategy

Approach: To solve the problem, we consider the combined valuation of each stone based on both Alice's and Bob's values. By maximizing the sum of their values during selection, each player can ensure they minimize the advantage of the other player who plays optimally. The steps are as follows:

  1. Create a list of tuples or arrays where each element combines Alice's valuation and Bob's valuation for each stone, along with the stone's index.
  2. Sort this list based on the descending order of the sum of Alice's and Bob's valuations (i.e., aliceValues[i] + bobValues[i]).
  3. Iterate through the sorted list, allowing Alice to pick stones at even-indexed turns and Bob at odd-indexed turns.
  4. Keep track of the points accumulated by Alice and Bob during their respective turns.
  5. Finally, compare the points to decide the result of the game: whether Alice wins, Bob wins, or it's a draw.

This solution involves combining the values in a tuple, sorting them based on their total, and then iterating over them while keeping track of whose turn it is to pick a stone, adding the appropriate value to their score.

Code

PythonJavaScriptC++

Python

JavaScript

C++

Complexity

Time Complexity: O(n log n), where n is the number of stones, due to the sorting step.
Space Complexity: O(n) due to storing the combined values list.

Try this approach in the editor →

Approach 2: Greedy Selection Based on Maximum Benefit

Approach: In this approach, we compute a benefit score for each stone, which helps in determining which stone provides the maximum relative utility to Alicia or Bob when picked. The benefit is taken as the difference between the players' valuations, specifically aliceValues[i] - bobValues[i]. We then sort stones based on absolute values of these benefits, but make choices considering the sign of the benefit to ensure optimal picking.

  1. Calculate benefits for each stone as the difference between Alice's and Bob's values, associating this benefit with both player's valuations and stone indices.
  2. Sort this benefits array based on the absolute value of benefits in descending order.
  3. Iterate over the sorted benefits list, allowing Alice to pick stones where benefits are positive and Bob where they are negative in descending order, building their scores.
  4. Compare scores at the end to decide the game's outcome.

This Java solution uses a strategy based on computing differences for benefits, sorting stones based on the absolute values of these benefits and distributing scores based on turn index parity.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n log n), necessary for sorting.
Space Complexity: O(n), resulting from the extra storage for the 'benefit' tuple array.

Try this approach in the editor →

Approach 3: 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.

Next, we let Alice and Bob pick stones alternately according to the order of vals. Alice picks the stones at even positions in vals, and Bob picks the stones at odd positions in vals. Finally, we compare the scores of Alice and Bob and return the corresponding result.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the arrays aliceValues and bobValues.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Maximize Combined Value Strategy

Time Complexity: O(n log n), where n is the number of stones, due to the sorting step.
Space Complexity: O(n) due to storing the combined values list.

Greedy Selection Based on Maximum Benefit

Time Complexity: O(n log n), necessary for sorting.
Space Complexity: O(n), resulting from the extra storage for the 'benefit' tuple array.

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 HeapO(n log n)O(n)Useful when stones must be selected dynamically or when demonstrating priority queue usage

Video Solution

1686. Stone Game VI || Leetcode • Aryan Mittal • 4,203 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Stone Game VI easy or hard?
Stone Game VI is generally considered a medium difficulty problem. The implementation is straightforward once you recognize the greedy insight of sorting by combined value, but identifying that key idea can take time during interviews.
Stone Game VI Python/Java solution
In Python or Java, compute the combined value aliceValues[i] + bobValues[i] for each stone, sort indices by this value in descending order, and simulate alternating turns. Alice adds aliceValues[i] to her score on her turns, while Bob adds bobValues[i] on his turns. After all stones are chosen, compare scores to determine the winner.
How to solve Stone Game VI in O(n)?
A strict O(n) solution is generally not possible because the strategy requires ordering stones by combined value, which requires sorting or a priority queue. Both standard implementations take O(n log n). Linear time would only be possible if the value range were small enough to use counting sort, which is not guaranteed by the constraints.
What is the best approach for Stone Game VI?
The best approach sorts stones by the combined value aliceValues[i] + bobValues[i] in descending order. Players then pick stones alternately following this order. This greedy strategy works because each stone affects both players' scores. The approach runs in O(n log n) time due to sorting.
Is Stone Game VI asked at Google/Amazon/Meta?
Stone Game VI represents a classic greedy and game-theory style interview problem. Variants of competitive picking problems appear in interviews at companies like Amazon, Google, and Meta where candidates must reason about optimal play and resource prioritization.
What data structure is used in Stone Game VI?
The typical solution uses arrays along with sorting to order stones by combined value. An alternative implementation uses a max heap or priority queue to repeatedly select the most impactful stone. Both approaches rely on greedy selection logic.
What is the time complexity of Stone Game VI?
The optimal solution runs in O(n log n) time because the stones are sorted by their combined value before simulating the game. The turn-by-turn score calculation afterward takes O(n). Space complexity is typically O(n) to store the combined pairs or indices.

Ready to solve this problem?

Practice Stone Game VI with our built-in code editor and test cases.

Practice on FleetCode
Previous

Stone Game

Next

Stone Game II