Stone Game III - Practice Coding Problems

Stone Game III - Problem

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.

The score of each player is the sum of the values of the stones taken. The score of each player is 0 initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob play optimally.

Return "Alice" if Alice will win, "Bob" if Bob will win, or "Tie" if they will end the game with the same score.

Input & Output

Example 1 — Alice Wins

$ Input: stoneValue = [1,-3,7,-4]

› Output: "Alice"

💡 Note: Alice takes 3 stones (1,-3,7) for score 5, Bob takes 1 stone (-4) for score -4. Alice wins 5 > -4.

Example 2 — Bob Wins

$ Input: stoneValue = [-1,-2,-3]

› Output: "Bob"

💡 Note: All values negative. Alice takes 1 stone (-1), Bob takes 2 stones (-2,-3) = -5. Bob wins since -5 > -1.

Example 3 — Tie Game

$ Input: stoneValue = [1,2,-3]

› Output: "Tie"

💡 Note: Alice takes 2 stones (1,2) = 3, Bob takes 1 stone (-3) = -3. Both have same total: 0.

Constraints

1 ≤ stoneValue.length ≤ 5 × 10⁴
-1000 ≤ stoneValue[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stone values: [1,-3,7,-4]

Game Play

Players alternate, taking 1-3 stones from start

Optimal Strategy

Alice takes [1,-3,7]=5, Bob takes [-4]=-4

Key Takeaway

🎯 Key Insight: Use DP to calculate maximum score difference each player can achieve from any position

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to track score differences rather than absolute scores. We can use dynamic programming to calculate the maximum advantage each player can achieve from any position. The optimal approach uses bottom-up DP with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n)	O(n)	Build solution iteratively from end to start
Top-Down DP with Memoization	O(n)	O(n)	Cache recursive results to avoid recomputation
Brute Force Recursion	O(3ⁿ)	O(n)	Try all possible moves recursively without memoization

Bottom-Up Dynamic Programming — Algorithm Steps

Create DP array where dp[i] represents max advantage from position i
Fill array backwards from end to start
For each position, try taking 1, 2, or 3 stones and choose maximum advantage

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create DP array, start from last position

Fill Backwards

For each position, calculate optimal score difference

Result

dp[0] gives Alice's advantage

Code -

solution.c — C

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

char* solution(int* stoneValue, int n) {
    if (n == 0) {
        return "Tie";
    }
    
    // dp[i] represents the maximum score difference the current player can achieve
    // starting from position i
    int* dp = (int*)calloc(n + 3, sizeof(int)); // Add padding to avoid bounds checking
    
    // Fill dp array backwards
    for (int i = n - 1; i >= 0; i--) {
        int currentSum = 0;
        int maxScore = INT_MIN;
        
        // Try taking 1, 2, or 3 stones
        int maxTake = (3 < n - i) ? 3 : n - i;
        for (int take = 1; take <= maxTake; take++) {
            currentSum += stoneValue[i + take - 1];
            // Current player's gain minus opponent's best response
            int score = currentSum - dp[i + take];
            if (score > maxScore) {
                maxScore = score;
            }
        }
        
        dp[i] = maxScore;
    }
    
    int aliceAdvantage = dp[0];
    free(dp);
    
    if (aliceAdvantage > 0) {
        return "Alice";
    } else if (aliceAdvantage < 0) {
        return "Bob";
    } else {
        return "Tie";
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int stoneValue[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        stoneValue[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char* result = solution(stoneValue, size);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through array, constant work per position

✓ Linear Growth

Space Complexity

O(n)

DP array of size n to store results

⚡ Linearithmic Space

28.4K 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

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler