Stone Game - Practice Coding Problems

Stone Game - Problem

Alice and Bob play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones across all the piles is odd, so there are no ties.

Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.

Input & Output

Example 1 — Basic Game

$ Input: piles = [5,3,7,1]

› Output: true

💡 Note: Alice takes 5 first, Bob takes 1, Alice takes 7, Bob takes 3. Alice gets 5+7=12, Bob gets 1+3=4. Alice wins with 12 > 4.

Example 2 — Different Strategy

$ Input: piles = [3,7,2,3]

› Output: true

💡 Note: Alice takes 3 first, Bob takes 3, Alice takes 2, Bob takes 7. Alice gets 3+2=5, Bob gets 3+7=10. Wait - Alice should take 3 from right! Alice takes 3, Bob takes 3, Alice takes 7, Bob takes 2. Alice gets 3+7=10, Bob gets 3+2=5. Alice wins.

Example 3 — Mathematical Insight

$ Input: piles = [1,100,2,200]

› Output: true

💡 Note: Even indices: 1+2=3, Odd indices: 100+200=300. Alice can force odd indices by taking from right first, guaranteeing she gets 300 > 3.

Constraints

2 ≤ piles.length ≤ 500
piles.length is even
1 ≤ piles[i] ≤ 500
sum(piles[i]) is odd

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stone piles: [5,3,7,1]

Strategy

Alice can force even or odd indices

Victory

Alice wins with optimal play

Key Takeaway

🎯 Key Insight: Alice can always force a win by controlling which indexed piles she accesses through strategic end selection

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is that Alice can always force a win due to the game's structure. With an even number of piles and odd total stones, Alice can choose to take all even-indexed or odd-indexed piles by controlling which end she takes from. The mathematical approach simply returns true in O(1) time, while dynamic programming approaches compute the actual optimal strategy in O(n²) time.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Simulation	O(2ⁿ)	O(n)	Simulate all possible game moves recursively
Mathematical Insight	O(1)	O(1)	Alice always wins due to game structure
Dynamic Programming with Memoization	O(n²)	O(n²)	Cache recursive results to avoid recomputation
Bottom-Up Dynamic Programming	O(n²)	O(n²)	Build solution iteratively using 2D DP table

Recursive Simulation — Algorithm Steps

Recursively try taking from left or right end
Alternate between Alice and Bob's turns
Return the maximum advantage achievable

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Move

Try taking from left or right end

Recurse

Let opponent play optimally on remaining piles

Backtrack

Return best advantage achievable

Code -

solution.c — C

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

int gameScore(int* piles, int left, int right) {
    if (left > right) {
        return 0;
    }
    
    int takeLeft = piles[left] - gameScore(piles, left + 1, right);
    int takeRight = piles[right] - gameScore(piles, left, right - 1);
    
    return takeLeft > takeRight ? takeLeft : takeRight;
}

bool solution(int* piles, int pilesSize) {
    return gameScore(piles, 0, pilesSize - 1) > 0;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int piles[1000];
    int count = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        piles[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(piles, count);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each position has 2 choices, creating exponential recursion tree

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals number of piles

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~25 min Avg. Time

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

Recursive Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler