Problem

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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

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

1
2
3
4
5
6

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 <= 10^5
  • 1 <= aliceValues[i], bobValues[i] <= 100

Solution

Method 1 - Greedy by Total Value

Intuition

Each player wants to maximize their own score, but since both know each other’s values, the optimal strategy is to always pick the stone with the highest combined value (aliceValues[i] + bobValues[i]) on each turn. This way, the player can maximize their own gain and minimize the opponent’s gain.

Approach

  • For each stone, compute the sum of Alice’s and Bob’s values.
  • Sort the stones in descending order of this sum.
  • Alternate picks: Alice picks first, then Bob, and so on.
  • Sum up Alice’s and Bob’s scores and compare at the end.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
        int n = aliceValues.size();
        vector<pair<int, int>> stones;
        for (int i = 0; i < n; ++i)
            stones.push_back({aliceValues[i] + bobValues[i], i});
        sort(stones.rbegin(), stones.rend());
        int alice = 0, bob = 0;
        for (int i = 0; i < n; ++i) {
            int idx = stones[i].second;
            if (i % 2 == 0) alice += aliceValues[idx];
            else bob += bobValues[idx];
        }
        if (alice > bob) return 1;
        if (alice < bob) return -1;
        return 0;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func stoneGameVI(aliceValues, bobValues []int) int {
    n := len(aliceValues)
    stones := make([][2]int, n)
    for i := 0; i < n; i++ {
        stones[i] = [2]int{aliceValues[i] + bobValues[i], i}
    }
    sort.Slice(stones, func(i, j int) bool {
        return stones[i][0] > stones[j][0]
    })
    alice, bob := 0, 0
    for i := 0; i < n; i++ {
        idx := stones[i][1]
        if i%2 == 0 {
            alice += aliceValues[idx]
        } else {
            bob += bobValues[idx]
        }
    }
    if alice > bob {
        return 1
    } else if alice < bob {
        return -1
    }
    return 0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;
class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        int[][] stones = new int[n][2];
        for (int i = 0; i < n; i++) {
            stones[i][0] = aliceValues[i] + bobValues[i];
            stones[i][1] = i;
        }
        Arrays.sort(stones, (a, b) -> b[0] - a[0]);
        int alice = 0, bob = 0;
        for (int i = 0; i < n; i++) {
            int idx = stones[i][1];
            if (i % 2 == 0) alice += aliceValues[idx];
            else bob += bobValues[idx];
        }
        if (alice > bob) return 1;
        if (alice < bob) return -1;
        return 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

fun stoneGameVI(aliceValues: IntArray, bobValues: IntArray): Int {
    val n = aliceValues.size
    val stones = List(n) { aliceValues[it] + bobValues[it] to it }.sortedByDescending { it.first }
    var alice = 0; var bob = 0
    for (i in 0 until n) {
        val idx = stones[i].second
        if (i % 2 == 0) alice += aliceValues[idx]
        else bob += bobValues[idx]
    }
    return when {
        alice > bob -> 1
        alice < bob -> -1
        else -> 0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def stoneGameVI(aliceValues: list[int], bobValues: list[int]) -> int:
    stones = sorted([(a+b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))], reverse=True)
    alice = bob = 0
    for i, (_, idx) in enumerate(stones):
        if i % 2 == 0:
            alice += aliceValues[idx]
        else:
            bob += bobValues[idx]
    if alice > bob:
        return 1
    if alice < bob:
        return -1
    return 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

pub fn stone_game_vi(alice_values: Vec<i32>, bob_values: Vec<i32>) -> i32 {
    let n = alice_values.len();
    let mut stones: Vec<(i32, usize)> = (0..n).map(|i| (alice_values[i] + bob_values[i], i)).collect();
    stones.sort_unstable_by(|a, b| b.0.cmp(&a.0));
    let (mut alice, mut bob) = (0, 0);
    for (i, &(_, idx)) in stones.iter().enumerate() {
        if i % 2 == 0 {
            alice += alice_values[idx];
        } else {
            bob += bob_values[idx];
        }
    }
    if alice > bob { 1 } else if alice < bob { -1 } else { 0 }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function stoneGameVI(aliceValues: number[], bobValues: number[]): number {
    const n = aliceValues.length;
    const stones = Array.from({length: n}, (_, i) => [aliceValues[i] + bobValues[i], i]);
    stones.sort((a, b) => b[0] - a[0]);
    let alice = 0, bob = 0;
    for (let i = 0; i < n; i++) {
        const idx = stones[i][1];
        if (i % 2 === 0) alice += aliceValues[idx];
        else bob += bobValues[idx];
    }
    if (alice > bob) return 1;
    if (alice < bob) return -1;
    return 0;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)