Stone Game VI - Practice Coding Problems

Stone Game VI - Problem

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

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 i-th 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.

Input & Output

Example 1 — Alice Wins

$ Input: aliceValues = [1,3], bobValues = [3,1]

› Output: 1

💡 Note: Combined values: [4,4]. Alice picks first stone (gains 1), Bob picks second (gains 1). Alice: 1, Bob: 1. Tie, so result is 0. Wait - let me recalculate: If Alice picks stone 0 (A:1,B:3), then Bob picks stone 1 (A:3,B:1) and gets 1 point. Alice:1, Bob:1 = tie. But if Alice picks stone 1 first (A:3,B:3), Bob gets stone 0 (A:1,B:3) and gets 3. Alice:3, Bob:3 = tie. Actually both lead to tie, so result is 0.

Example 2 — Different Values

$ Input: aliceValues = [1,2], bobValues = [3,1]

› Output: 0

💡 Note: Combined values: stone 0 has sum 4, stone 1 has sum 3. Alice picks stone 0 (gains 1), Bob picks stone 1 (gains 1). Alice: 1, Bob: 1. Draw.

Example 3 — Clear Winner

$ Input: aliceValues = [2,4,3], bobValues = [1,1,2]

› Output: 1

💡 Note: Combined values: [3,5,5]. Sorted order: stone 1 (sum 5), stone 2 (sum 5), stone 0 (sum 3). Alice picks stone 1 (gains 4), Bob picks stone 2 (gains 2), Alice picks stone 0 (gains 2). Alice: 6, Bob: 2. Alice wins.

Constraints

n == aliceValues.length == bobValues.length
1 ≤ n ≤ 10⁵
1 ≤ aliceValues[i], bobValues[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays showing how Alice and Bob value each stone

Process

Players alternate turns picking stones optimally

Output

1 if Alice wins, -1 if Bob wins, 0 for draw

Key Takeaway

🎯 Key Insight: The optimal strategy is to prioritize stones by their combined value impact - maximizing your gain while minimizing opponent's potential gain

Asked in

G Google 12 a Amazon 8 f Facebook 6

The key insight is that picking a stone gives you points AND denies your opponent their points for that stone. The optimal strategy is to sort stones by combined value (aliceValues[i] + bobValues[i]) and have players pick greedily from highest impact stones first. Best approach uses greedy sorting in O(n log n) time, O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Combined Value Priority	O(n log n)	O(n)	Sort stones by sum of both players' values and pick greedily
Brute Force - Game Tree Exploration	O(n!)	O(n)	Recursively explore all possible game sequences with optimal play

Greedy - Combined Value Priority — Algorithm Steps

Create pairs of (combined_value, index) for each stone
Sort stones by combined value in descending order
Simulate the game with players picking optimally from sorted order

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Impact

Sum Alice and Bob values for each stone

Sort by Priority

Order stones by total impact (highest first)

Simulate Game

Players alternate picking from sorted order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int combined;
    int index;
} Stone;

int compare(const void* a, const void* b) {
    Stone* stoneA = (Stone*)a;
    Stone* stoneB = (Stone*)b;
    return stoneB->combined - stoneA->combined; // Descending order
}

int solution(int* aliceValues, int* bobValues, int n) {
    // Create array of stones with combined values
    Stone* stones = (Stone*)malloc(n * sizeof(Stone));
    for (int i = 0; i < n; i++) {
        stones[i].combined = aliceValues[i] + bobValues[i];
        stones[i].index = i;
    }
    
    // Sort by combined value in descending order
    qsort(stones, n, sizeof(Stone), compare);
    
    // Simulate game with optimal play
    int aliceScore = 0;
    int bobScore = 0;
    
    for (int turn = 0; turn < n; turn++) {
        int stoneIndex = stones[turn].index;
        if (turn % 2 == 0) {  // Alice's turn
            aliceScore += aliceValues[stoneIndex];
        } else {  // Bob's turn
            bobScore += bobValues[stoneIndex];
        }
    }
    
    free(stones);
    
    if (aliceScore > bobScore) {
        return 1;
    } else if (bobScore > aliceScore) {
        return -1;
    } else {
        return 0;
    }
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing for arrays
    int aliceValues[100], bobValues[100];
    int n = 0;
    
    char* token = strtok(line1 + 1, ",]");
    while (token != NULL) {
        aliceValues[n] = atoi(token);
        token = strtok(NULL, ",]");
        n++;
    }
    
    token = strtok(line2 + 1, ",]");
    int idx = 0;
    while (token != NULL) {
        bobValues[idx] = atoi(token);
        token = strtok(NULL, ",]");
        idx++;
    }
    
    printf("%d\n", solution(aliceValues, bobValues, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting stones by combined value takes O(n log n), simulation takes O(n)

⚡ Linearithmic

Space Complexity

O(n)

Array to store stone indices and their combined values for sorting

⚡ Linearithmic Space

25.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Combined Value Priority — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler