Stone Game VIII - Practice Coding Problems

Stone Game VIII - Problem

Array Math Dynamic Programming Prefix Sum Game Theory Hard

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones' values to the player's score.
Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is to minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.

Input & Output

Example 1 — Small Array

$ Input: stones = [-1,2,-3,4,-5]

› Output: 5

💡 Note: Alice can take the first 4 stones (sum = -1+2+(-3)+4 = 2), then Bob must take the remaining stones [2,-5] (sum = -3), giving Alice advantage of 2-(-3) = 5.

Example 2 — All Positive

$ Input: stones = [7,-6,5,10,5,-2,-6]

› Output: 13

💡 Note: Alice plays optimally to maximize score difference, achieving a final advantage of 13.

Example 3 — Minimum Size

$ Input: stones = [-10,20]

› Output: 10

💡 Note: Alice must take both stones (sum = 10), Bob gets nothing, so difference is 10.

Constraints

3 ≤ stones.length ≤ 10⁴
-10⁴ ≤ stones[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Game Setup

Alice and Bob alternate turns, Alice starts first

Move Rules

Take ≥2 leftmost stones, add sum to score, replace with single stone

Objective

Alice maximizes (her score - Bob's score), Bob minimizes it

Key Takeaway

🎯 Key Insight: This is a minimax problem where optimal play requires dynamic programming to evaluate all possible future game states

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is recognizing this as a minimax game theory problem where we can use dynamic programming with prefix sums. After each move, we have a subarray starting from some position. The optimal approach uses DP with prefix sums where dp[i] represents the maximum score difference achievable from position i. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Game Theory	O(n!)	O(n!) + O(n)	Cache recursive results to avoid recomputing identical game states
Dynamic Programming with Prefix Sums	O(n²)	O(n)	Use prefix sums and DP to compute optimal scores efficiently
Recursive Game Tree	O(2^n)	O(n)	Recursively try all possible moves for both players

Memoized Game Theory — Algorithm Steps

Convert stone array to string key for memoization
Check cache before recursive computation
Store and return computed results

Visualization

Tap to expand

Step-by-Step Walkthrough

First Calculation

Compute result for a game state and store in cache

Cache Hit

Same state encountered again - return cached result

Performance Boost

Avoid recomputing identical subproblems

Code -

solution.c — C

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

#define MEMO_SIZE 10000

typedef struct {
    char key[1000];
    int value;
    int used;
} MemoEntry;

MemoEntry memo[MEMO_SIZE];

int hash_string(const char* str) {
    int hash = 0;
    while (*str) {
        hash = hash * 31 + *str;
        str++;
    }
    return abs(hash) % MEMO_SIZE;
}

int get_memo(const char* key) {
    int idx = hash_string(key);
    while (memo[idx].used && strcmp(memo[idx].key, key) != 0) {
        idx = (idx + 1) % MEMO_SIZE;
    }
    return memo[idx].used ? memo[idx].value : INT_MIN;
}

void set_memo(const char* key, int value) {
    int idx = hash_string(key);
    while (memo[idx].used && strcmp(memo[idx].key, key) != 0) {
        idx = (idx + 1) % MEMO_SIZE;
    }
    strcpy(memo[idx].key, key);
    memo[idx].value = value;
    memo[idx].used = 1;
}

int minimax(int* remainingStones, int size, int isAliceTurn) {
    char key[1000] = "";
    for (int i = 0; i < size; i++) {
        char temp[20];
        sprintf(temp, "%d,", remainingStones[i]);
        strcat(key, temp);
    }
    strcat(key, isAliceTurn ? "T" : "F");
    
    int cached = get_memo(key);
    if (cached != INT_MIN) return cached;
    
    if (size <= 1) {
        set_memo(key, 0);
        return 0;
    }
    
    int bestScore = isAliceTurn ? INT_MIN : INT_MAX;
    
    for (int take = 2; take <= size; take++) {
        int takenSum = 0;
        for (int i = 0; i < take; i++) {
            takenSum += remainingStones[i];
        }
        
        int* newStones = (int*)malloc((size - take + 1) * sizeof(int));
        newStones[0] = takenSum;
        for (int i = take; i < size; i++) {
            newStones[i - take + 1] = remainingStones[i];
        }
        
        int futureScore = minimax(newStones, size - take + 1, !isAliceTurn);
        
        if (isAliceTurn) {
            int currentScore = takenSum + futureScore;
            if (currentScore > bestScore) {
                bestScore = currentScore;
            }
        } else {
            int currentScore = -takenSum + futureScore;
            if (currentScore < bestScore) {
                bestScore = currentScore;
            }
        }
        
        free(newStones);
    }
    
    set_memo(key, bestScore);
    return bestScore;
}

int solution(int* stones, int size) {
    memset(memo, 0, sizeof(memo));
    if (size <= 1) return 0;
    return minimax(stones, size, 1);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int stones[1000];
    int size = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        stones[size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(stones, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Number of unique game states is still very large, though reduced by memoization

⚠ Quadratic Growth

Space Complexity

O(n!) + O(n)

Memoization table stores many game states plus recursion stack

⚠ Quadratic Space

28.5K Views

Medium Frequency

~35 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

Memoized Game Theory — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler