Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1686. Stone Game VI - Leetcode Solution

Code Implementation

class Solution:
    def stoneGameVI(self, aliceValues, bobValues):
        n = len(aliceValues)
        stones = sorted(
            zip(aliceValues, bobValues),
            key=lambda x: -(x[0] + x[1])
        )
        alice, bob = 0, 0
        for i, (a, b) in enumerate(stones):
            if i % 2 == 0:
                alice += a
            else:
                bob += b
        if alice > bob:
            return 1
        elif alice < bob:
            return -1
        else:
            return 0
      
class Solution {
public:
    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
        int n = aliceValues.size();
        vector<pair<int, pair<int, int>>> stones;
        for (int i = 0; i < n; ++i) {
            stones.push_back({aliceValues[i] + bobValues[i], {aliceValues[i], bobValues[i]}});
        }
        sort(stones.rbegin(), stones.rend());
        int alice = 0, bob = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                alice += stones[i].second.first;
            else
                bob += stones[i].second.second;
        }
        if (alice > bob) return 1;
        else if (alice < bob) return -1;
        else return 0;
    }
};
      
class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        int[][] stones = new int[n][3];
        for (int i = 0; i < n; i++) {
            stones[i][0] = aliceValues[i] + bobValues[i];
            stones[i][1] = aliceValues[i];
            stones[i][2] = bobValues[i];
        }
        Arrays.sort(stones, (a, b) -> b[0] - a[0]);
        int alice = 0, bob = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0)
                alice += stones[i][1];
            else
                bob += stones[i][2];
        }
        if (alice > bob) return 1;
        else if (alice < bob) return -1;
        else return 0;
    }
}
      
var stoneGameVI = function(aliceValues, bobValues) {
    const n = aliceValues.length;
    let stones = [];
    for (let i = 0; i < n; i++) {
        stones.push([aliceValues[i] + bobValues[i], aliceValues[i], bobValues[i]]);
    }
    stones.sort((a, b) => b[0] - a[0]);
    let alice = 0, bob = 0;
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) alice += stones[i][1];
        else bob += stones[i][2];
    }
    if (alice > bob) return 1;
    else if (alice < bob) return -1;
    else return 0;
};

Problem Description

In Stone Game VI, you are given two integer arrays, aliceValues and bobValues, each of length n. There are n stones, and the i-th stone has a value aliceValues[i] for Alice and bobValues[i] for Bob. Alice and Bob take turns picking up stones (Alice starts first), and once a stone is picked, it cannot be chosen again. Each player adds the value of the stone they pick (according to their own array) to their score. The game continues until all stones are taken. The goal is to determine who will win if both play optimally:
  • Return 1 if Alice wins (her score is higher)
  • Return -1 if Bob wins
  • Return 0 if it's a tie
Key constraints:
  • Each stone can be picked only once
  • Both players play optimally to maximize their own scores
  • There is always one valid way to pick stones (no ties in picking order)

Thought Process

At first glance, the problem looks like a variation of a turn-based picking game, where each player wants to maximize their own score. A brute-force approach would be to simulate every possible sequence of picks, but this quickly becomes infeasible as n grows, because the number of possible pick orders is n! (factorial time).

To optimize, we should look for a strategy that allows both players to make the best possible pick at each turn. Since both players care about maximizing their own score, but also want to deny the other player high-value stones, we need a way to evaluate the importance of each stone for both players.

The key insight is that the "combined value" of a stone (i.e., aliceValues[i] + bobValues[i]) tells us how much a stone is "contested" between the two players. Picking stones with the highest combined value first ensures that the most valuable options are taken early, minimizing what the opponent can gain from them.

Solution Approach

The optimal approach is based on sorting the stones by their total importance to both players. Here’s how we solve the problem step by step:
  1. Pair Each Stone's Values: For each stone, combine its Alice and Bob values into a tuple or object, along with its index if needed.
  2. Sort Stones by Combined Value: Sort all stones in descending order of aliceValues[i] + bobValues[i]. This ensures that, on each turn, the player picks the stone that is most valuable overall.
  3. Simulate Picking Turns: Loop through the sorted stones. For each turn:
    • If it's Alice's turn (even index in the sorted list), add aliceValues[i] to her score.
    • If it's Bob's turn (odd index), add bobValues[i] to his score.
  4. Compare Final Scores: At the end, compare Alice's and Bob's totals and return the result as specified.

This greedy approach works because picking the highest combined value stone either maximizes your gain or minimizes your opponent's possible gain, which is exactly what optimal play requires in this context.

Example Walkthrough

Let's consider the example:
aliceValues = [1, 3]
bobValues = [2, 1]

  1. Pair and Sum:
    • Stone 0: (1, 2), sum = 3
    • Stone 1: (3, 1), sum = 4
  2. Sort by Combined Value:
    • Stone 1: sum = 4
    • Stone 0: sum = 3
  3. Simulate Picks:
    • Turn 1 (Alice): Picks Stone 1, gets 3 points (Alice: 3, Bob: 0)
    • Turn 2 (Bob): Picks Stone 0, gets 2 points (Alice: 3, Bob: 2)
  4. Result: Alice has 3, Bob has 2. Alice wins, so output is 1.

This process ensures that the player who can get the most out of the available stones does so, while also denying the opponent their best options.

Time and Space Complexity

  • Brute-force approach: Would try every possible pick sequence, leading to O(n!) time and O(n) space for recursion stack, which is not practical.
  • Optimized approach:
    • Sorting: Sorting the stones by combined value takes O(n log n) time.
    • Simulation: Looping through the stones is O(n).
    • Total Time Complexity: O(n log n)
    • Space Complexity: O(n) for storing the sorted stones.

This is efficient and suitable for the problem's constraints.

Summary

The key to solving Stone Game VI is to recognize that the most optimal move is to always pick the stone with the highest combined value for both players. By sorting the stones and alternating picks, both Alice and Bob maximize their own points while minimizing their opponent's opportunities. This greedy approach is both efficient and elegant, reducing the problem from a factorial brute-force search to a simple sort and simulation, making it accessible and efficient for any reasonable input size.