Stone Game

Description

Alice and Bob are playing a game with piles of stones arranged in a row. There are an even number of piles, and each pile contains a positive number of stones given by piles[i].

The rules are simple: players take turns, with Alice going first. On each turn, a player must take the entire pile of stones from either the beginning (leftmost) or the end (rightmost) of the remaining row. The game ends when all piles have been taken.

The player who collects the most stones in total wins. The total number of stones across all piles is odd, so ties are impossible.

Both players play optimally — meaning each player always makes the best possible move to maximize their own total. Return true if Alice wins the game, or false if Bob wins.

Examples

Example 1

Input: piles = [5, 3, 4, 5]

Output: true

Explanation: Alice starts first and can take either the first 5 or the last 5.

If Alice takes the first 5, the row becomes [3, 4, 5]. No matter what Bob does, Alice can guarantee at least 9 stones:
- If Bob takes 3, Alice takes 5. Alice: 5+5=10, Bob: 3+4=7.
- If Bob takes 5, Alice takes 4. Alice: 5+4=9, Bob: 5+3=8.
In both cases Alice wins, so the answer is true.

Example 2

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

Output: true

Explanation: With optimal play, Alice can guarantee 10 stones against Bob's 5.

Alice takes 3 (right end). Row becomes [3, 7, 2].
Bob takes 3 (left) or 2 (right). Either way:
- If Bob takes 2: row is [3, 7]. Alice takes 7. Alice: 3+7=10, Bob: 2+3=5.
- If Bob takes 3: row is [7, 2]. Alice takes 7. Alice: 3+7=10, Bob: 3+2=5.
Alice always collects 10 stones and wins.

Constraints

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

Editorial

Brute Force

Intuition

The most natural way to solve a two-player game is to simulate every possible move. At each turn, the current player has exactly two choices: take from the left end or the right end. We need to explore all possible sequences of moves to determine who wins when both players play their best.

A clever simplification is to track the score difference rather than individual scores. Define dfs(l, r) as the maximum advantage (score difference) the current player can achieve when the remaining piles span indices l to r.

Why does this work? When the current player takes piles[l], they gain piles[l] points. But then the opponent plays optimally on the remaining range [l+1, r], and the opponent's advantage there is dfs(l+1, r). From the current player's perspective, the opponent's advantage is their disadvantage. So the net advantage of taking the left pile is piles[l] - dfs(l+1, r). Similarly, taking the right pile yields piles[r] - dfs(l, r-1).

The current player picks whichever option gives the larger advantage. When there are no piles left (l > r), the advantage is 0. Finally, Alice wins if dfs(0, n-1) > 0.

Without memoization, this recursion explores every possible game tree, leading to exponential time complexity.

Step-by-Step Explanation

Let's trace through piles = [5, 3, 4, 5]. We compute dfs(l, r) = max advantage for current player on piles[l..r].

Step 1: Start with dfs(0, 3) — Alice faces all 4 piles [5, 3, 4, 5].

Step 2: Alice tries taking left (pile 5). We need dfs(1, 3) for Bob on [3, 4, 5].

Step 3: Bob at dfs(1, 3) tries left (pile 3). We need dfs(2, 3) for [4, 5].

Step 4: At dfs(2, 3), we hit base cases: dfs(3, 3) = 5 (single pile, take it) and dfs(2, 2) = 4.

dfs(2, 3) = max(4 - 5, 5 - 4) = max(-1, 1) = 1. Taking right (pile 5) is better.

Step 5: Bob at dfs(1, 3) also tries right (pile 5). We need dfs(1, 2) for [3, 4].

Step 6: At dfs(1, 2), base cases: dfs(2, 2) = 4 (REPEATED computation!) and dfs(1, 1) = 3.

dfs(1, 2) = max(3 - 4, 4 - 3) = max(-1, 1) = 1.

Step 7: Now dfs(1, 3) = max(3 - 1, 5 - 1) = max(2, 4) = 4. Bob's advantage on [3, 4, 5] is 4.

Step 8: Alice also tries taking right (pile 5). We need dfs(0, 2) for [5, 3, 4].

dfs(0, 2) requires dfs(1, 2) = 1 (REPEATED!) and dfs(0, 1) = max(5-3, 3-5) = 2.
dfs(0, 2) = max(5 - 1, 4 - 2) = max(4, 2) = 4.

Step 9: Finally, dfs(0, 3) = max(5 - 4, 5 - 4) = max(1, 1) = 1.

Step 10: Since 1 > 0, Alice has a positive advantage. She wins! Alice scores (17 + 1)/2 = 9, Bob scores (17 - 1)/2 = 8.

Brute Force — Exploring All Game States — Watch how the recursion explores every possible sequence of moves, branching at each decision point. Notice the repeated subproblems that cause exponential blowup.

Algorithm

Define recursive function dfs(l, r) that returns the maximum score advantage the current player can achieve on piles[l..r]
Base case: if l > r, return 0 (no piles left, no advantage)
Recursive case: return max(piles[l] - dfs(l+1, r), piles[r] - dfs(l, r-1))
- Taking left pile: gain piles[l], opponent gets advantage dfs(l+1, r)
- Taking right pile: gain piles[r], opponent gets advantage dfs(l, r-1)
Call dfs(0, n-1) and return true if the result is positive (Alice wins)

Code

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return dfs(piles, 0, piles.size() - 1) > 0;
    }

    int dfs(vector<int>& piles, int l, int r) {
        if (l > r) return 0;
        int takeLeft = piles[l] - dfs(piles, l + 1, r);
        int takeRight = piles[r] - dfs(piles, l, r - 1);
        return max(takeLeft, takeRight);
    }
};

class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        def dfs(l: int, r: int) -> int:
            if l > r:
                return 0
            take_left = piles[l] - dfs(l + 1, r)
            take_right = piles[r] - dfs(l, r - 1)
            return max(take_left, take_right)

        return dfs(0, len(piles) - 1) > 0

class Solution {
    public boolean stoneGame(int[] piles) {
        return dfs(piles, 0, piles.length - 1) > 0;
    }

    private int dfs(int[] piles, int l, int r) {
        if (l > r) return 0;
        int takeLeft = piles[l] - dfs(piles, l + 1, r);
        int takeRight = piles[r] - dfs(piles, l, r - 1);
        return Math.max(takeLeft, takeRight);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each state (l, r), we make two recursive calls. Without memoization, the same subproblems are recomputed many times. The recursion tree has depth n (each call reduces the range by 1), and each node branches into 2 children. This gives roughly 2^n total calls in the worst case.

Space Complexity: O(n)

The recursion depth is at most n (the range shrinks by 1 each level). Each stack frame uses O(1) space, so the call stack uses O(n) space total.

Why This Approach Is Not Efficient

The brute force recursion has O(2^n) time complexity because it recomputes the same subproblems over and over. For example, with just n=4 piles, we already computed dfs(2,2) and dfs(1,2) multiple times. With n up to 500, 2^500 is astronomically large — far beyond any computer's capability.

The root cause is overlapping subproblems. There are only O(n²) unique states (each defined by a pair (l, r) where 0 ≤ l ≤ r < n), but the recursion visits many of them repeatedly. If we could compute each state exactly once and store the result, we would reduce the time from O(2^n) to O(n²). This is exactly what dynamic programming provides — memoize each (l, r) result so it is never recomputed.

Bar chart comparing O(2^n) brute force time vs O(n²) DP time for n=500

Better Approach - Interval Dynamic Programming

Intuition

The brute force already has the correct recurrence — the only problem is redundant computation. We can fix this by storing results in a 2D table.

Define dp[l][r] as the maximum score advantage the current player can achieve when the remaining piles are piles[l..r]. The recurrence is the same:

dp[l][r] = max(piles[l] - dp[l+1][r], piles[r] - dp[l][r-1])

Base case: dp[i][i] = piles[i] (one pile left, current player takes it, advantage = piles[i]).

We fill the table bottom-up by increasing gap length (the difference r - l). This ensures that when we compute dp[l][r], the values dp[l+1][r] and dp[l][r-1] (both smaller ranges) are already available.

The answer is dp[0][n-1] > 0.

This is a classic interval DP pattern: we solve subproblems on progressively larger subranges, building up from single-element ranges to the full range. Each cell in the table is computed exactly once in O(1) time, giving O(n²) total time.

Step-by-Step Explanation

Let's trace the bottom-up DP table for piles = [5, 3, 4, 5].

Step 1 — Initialize diagonal (gap = 0): Each single pile has advantage equal to its value.

dp[0][0] = 5, dp[1][1] = 3, dp[2][2] = 4, dp[3][3] = 5

Step 2 — Fill gap = 1 (two adjacent piles):

dp[0][1]: piles [5, 3]. max(5 - dp[1][1], 3 - dp[0][0]) = max(5-3, 3-5) = max(2, -2) = 2. Take left (5) for +2 advantage.

Step 3: dp[1][2]: piles [3, 4]. max(3 - dp[2][2], 4 - dp[1][1]) = max(3-4, 4-3) = max(-1, 1) = 1. Take right (4).

Step 4: dp[2][3]: piles [4, 5]. max(4 - dp[3][3], 5 - dp[2][2]) = max(4-5, 5-4) = max(-1, 1) = 1. Take right (5).

Step 5 — Fill gap = 2 (three piles):

dp[0][2]: piles [5, 3, 4]. max(5 - dp[1][2], 4 - dp[0][1]) = max(5-1, 4-2) = max(4, 2) = 4. Take left (5).

Step 6: dp[1][3]: piles [3, 4, 5]. max(3 - dp[2][3], 5 - dp[1][2]) = max(3-1, 5-1) = max(2, 4) = 4. Take right (5).

Step 7 — Fill gap = 3 (all four piles):

dp[0][3]: piles [5, 3, 4, 5]. max(5 - dp[1][3], 5 - dp[0][2]) = max(5-4, 5-4) = max(1, 1) = 1.

Step 8: dp[0][3] = 1 > 0. Alice wins! Each cell was computed exactly once — no redundancy.

Interval DP — Filling the Table Diagonally — Watch how we fill the DP table diagonal by diagonal, from single piles (gap=0) up to the full range (gap=3). Each cell is computed once using previously filled cells.

Algorithm

Create an n×n DP table initialized to 0
Fill base cases: for each i, set dp[i][i] = piles[i]
Fill the table by increasing gap length (gap = 1 to n-1):
- For each starting index l from 0 to n-1-gap:
  - Set r = l + gap
  - dp[l][r] = max(piles[l] - dp[l+1][r], piles[r] - dp[l][r-1])
Return dp[0][n-1] > 0

Code

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }

        for (int gap = 1; gap < n; gap++) {
            for (int l = 0; l + gap < n; l++) {
                int r = l + gap;
                dp[l][r] = max(piles[l] - dp[l + 1][r],
                               piles[r] - dp[l][r - 1]);
            }
        }

        return dp[0][n - 1] > 0;
    }
};

class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = piles[i]

        for gap in range(1, n):
            for l in range(n - gap):
                r = l + gap
                dp[l][r] = max(piles[l] - dp[l + 1][r],
                               piles[r] - dp[l][r - 1])

        return dp[0][n - 1] > 0

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }

        for (int gap = 1; gap < n; gap++) {
            for (int l = 0; l + gap < n; l++) {
                int r = l + gap;
                dp[l][r] = Math.max(piles[l] - dp[l + 1][r],
                                     piles[r] - dp[l][r - 1]);
            }
        }

        return dp[0][n - 1] > 0;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We fill an n×n table where only the upper triangle (cells with l ≤ r) is used. That gives n×(n+1)/2 ≈ n²/2 cells. Each cell is computed in O(1) time using the recurrence. Total: O(n²).

Space Complexity: O(n²)

The 2D DP table requires n×n space. Only the upper triangle is meaningful, but we allocate the full table for simplicity.

Why This Approach Is Not Efficient

The interval DP solution is efficient and correct for the general game — it runs in O(n²) time which easily handles n=500. However, this specific problem has a hidden mathematical structure that makes computation unnecessary.

Notice the constraints carefully: the number of piles is even and the total sum is odd. These aren't arbitrary restrictions — they guarantee a specific structural property. Because there's an even number of piles, Alice (the first player) has a powerful strategic advantage: she can always force herself to collect either all even-indexed piles or all odd-indexed piles.

Since the total sum is odd, the even-indexed and odd-indexed groups must have different sums. Alice simply calculates which group has more stones and forces that outcome. This means the answer is always true — no DP table needed. We can solve the problem in O(1) time.

Optimal Approach - Mathematical Observation

Intuition

Here is a beautiful mathematical insight that eliminates all computation.

Color the piles alternately: call even-indexed piles (indices 0, 2, 4, ...) "red" and odd-indexed piles (indices 1, 3, 5, ...) "blue". Since there are an even number of piles, the arrangement looks like: Red, Blue, Red, Blue, ..., Red, Blue.

Now observe what happens on Alice's first move:

If Alice takes from the left (index 0, a Red pile), the remaining row starts with Blue on the left and ends with Blue on the right. Both ends are Blue! Bob is forced to take a Blue pile.
If Alice takes from the right (index n-1, a Blue pile), the remaining row starts with Red on the left and ends with Red on the right. Both ends are Red! Bob is forced to take a Red pile.

After Bob's forced move, Alice again faces two ends of the same color — the color she chose. This pattern continues throughout the entire game. Alice can force herself to collect all Red piles or all Blue piles.

Since the total sum is odd, the Red sum and Blue sum must be different (they can't both be equal — that would make the total even). Alice calculates both sums upfront and picks the larger group.

Therefore, Alice always wins. The answer is simply return true.

Diagram showing piles [5,3,4,5] colored alternately red and blue, with Alice's two strategies

Step-by-Step Explanation

Let's trace through piles = [5, 3, 4, 5] to see how Alice forces a win.

Step 1: Label piles by index parity:

Even-indexed (Red): piles[0]=5, piles[2]=4. Sum = 9.
Odd-indexed (Blue): piles[1]=3, piles[3]=5. Sum = 8.
9 > 8, so Alice will use the "take all even-indexed" strategy.

Step 2: Alice takes piles[0]=5 (left end, even-indexed). Remaining: [3, 4, 5].

Left end is piles[1]=3 (odd). Right end is piles[3]=5 (odd). Both ends are odd-indexed!

Step 3: Bob must pick an odd-indexed pile (no choice). Say Bob takes piles[3]=5 (right). Remaining: [3, 4].

Left end is piles[1]=3 (odd). Right end is piles[2]=4 (even). Alice picks even.

Step 4: Alice takes piles[2]=4 (right, even-indexed). Remaining: [3].

Step 5: Bob takes piles[1]=3 (only option, odd-indexed).

Step 6: Final: Alice collected {5, 4} = 9 (all even-indexed). Bob collected {5, 3} = 8 (all odd-indexed). Alice wins 9 > 8.

Step 7: This works regardless of Bob's choices — Alice always controls which color she gets.

Mathematical Proof — Alice Forces Even-Indexed Piles — Watch how Alice systematically takes all even-indexed piles, leaving Bob no choice but to take odd-indexed ones. The parity structure guarantees this strategy always works.

Algorithm

Return true

That's it. The mathematical proof guarantees Alice always wins when:

The number of piles is even
The total sum is odd
Both players play optimally

Alice can always force collecting either all even-indexed or all odd-indexed piles, and since the total is odd, one group must be strictly larger. She picks the larger group.

Code

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        // Alice can always force a win with even pile count
        // and odd total sum. She chooses all even-indexed or
        // all odd-indexed piles — whichever group is larger.
        return true;
    }
};

class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        # Alice can always force a win with even pile count
        # and odd total sum. She chooses all even-indexed or
        # all odd-indexed piles — whichever group is larger.
        return True

class Solution {
    public boolean stoneGame(int[] piles) {
        // Alice can always force a win with even pile count
        // and odd total sum. She chooses all even-indexed or
        // all odd-indexed piles — whichever group is larger.
        return true;
    }
}

Complexity Analysis

Time Complexity: O(1)

We return a constant value without examining the input at all. No loops, no recursion, no computation.

Space Complexity: O(1)

No additional data structures are used. We only return a boolean constant.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Stone Game

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Interval Dynamic Programming

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Mathematical Observation

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis