1140. Stone Game II | LeetCode Daily Python Solution — grab 2 piles now? You still lose

Introduction

Stone Game II shows up on interview lists because it punishes the instinct that usually serves you well: take the biggest move available right now. In most greedy problems, grabbing the best immediate option is either optimal or close to it. Here, grabbing more stones on your turn can directly hand your opponent a bigger turn right after, and you end up worse off than if you'd taken less.

That single insight — that your move changes the rules for your opponent, not just the score — is what interviewers are actually testing. They want to see whether you can recognize a two-player optimization problem, compress a messy game history into a small state, and reach for memoized recursion instead of trying to brute-force every possible sequence of moves.

It's also a genuinely useful pattern outside of interviews. Any system where two agents alternate over a shrinking resource — auction bidding, turn-based game AI, adversarial scheduling — reduces to the same shape: define the state, define the recurrence, cache it.

Problem Overview

You're given a row of stone piles. Alice and Bob take turns removing piles from the front of the row only — you can never reach into the middle. Alice always goes first.

There's a shared limit, M, that starts at 1. On any turn, a player can take between 1 and 2M piles from the front. After the move, M is updated to be the larger of its old value or however many piles were just taken — so the limit never shrinks, only grows or stays the same.

Both players play optimally, each trying to maximize their own total stone count. The question: how many stones does Alice end up with?

The tricky part is that M isn't fixed — it's a resource both players are indirectly fighting over. Taking a big chunk of piles boosts M for everyone, including your opponent's next turn.

Example

Piles: [2, 7, 9, 4, 4] (26 stones total).

If both players play optimally, Alice finishes with 10 stones and Bob gets the remaining 16.

Here's why grabbing greedily fails: if Alice takes 2 piles right away (2 + 7 = 9), M becomes 2, and Bob can now take up to 4 piles. Bob takes the rest — 9 + 4 + 4 = 17 — and Alice is stuck with only 9.

Instead, Alice takes just 1 pile (2). M stays at 1, so Bob can take at most 2 piles. Bob takes 7 + 9 = 16, leaving Alice 4 + 4 = 8 more, for a total of 2 + 4 + 4 = 10. Taking less right now wins.

Intuition

The naive instinct is to track the entire game: which piles are gone, whose turn it is, what's been taken so far. That's far too much state to search directly.

The key realization: none of the history matters. Not which piles were taken, not who took them, not in what order. All that matters right now is:

1. Where you are in the row (an index).
2. What your current pick limit is.

Call this the Growing Window — the limit only ever grows, never shrinks. Those two numbers, (index, limit), fully describe every future outcome from this point forward. That's what makes the problem tractable: instead of exploring an exponential tree of pile sequences, you solve each (index, limit) state exactly once and cache the answer.

The second piece of intuition is about scoring. You don't track "Alice's total" and "Bob's total" separately through the recursion. Instead, at each state, you compute: everything remaining minus whatever your opponent scores best starting from the state you leave them in. Since both players are optimal and stones don't disappear, this single formula captures both players' incentives at once.

Brute Force Solution

Idea: At every state, try every legal number of piles to take (1 through 2*limit), recursively simulate the rest of the game for each choice, and pick whichever leaves you the best outcome — without caching anything.

Algorithm:

1. Recursively define best(index, limit).
2. Base case: if no piles remain, return 0.
3. Try every x from 1 to 2*limit, recursively computing what's left after taking x piles, minus the opponent's best response.
4. Return the max.

Advantages: Simple to reason about — it's a direct translation of the rules.

Disadvantages: Without memoization, the same (index, limit) state gets recomputed enormously many times, since different move sequences can land you back at an identical state. This blows up exponentially and is unusable beyond tiny inputs.

Complexity: Time is exponential — roughly O(2^n) in the worst case. Space is O(n) for the recursion stack.

Optimal Solution

The optimal solution keeps the exact same recursive shape but adds two things: memoization on the (index, limit) state, and suffix sums so "everything remaining" is an O(1) lookup instead of a re-sum every time.

Suffix sums: Precompute, for every starting index, the total of every pile from that index to the end of the row. Walking backward from the end:

suffix[i] = piles[i] + suffix[i + 1]

At index 0, suffix[0] is the total of the whole row.

State: (index, limit) — where you are, and the largest number of piles you're currently allowed to take.

Recurrence:

best(index, limit) = suffix[index] - min over x in [1, 2*limit] of best(index + x, max(limit, x))

Since suffix[index] is fixed for a given index, maximizing your own score is equivalent to minimizing what you leave your opponent's best response to be — which is why the formula subtracts the opponent's best future score.

Two early exits keep this fast:

• If index == len(piles), nothing is left — return 0.
• If 2 * limit >= len(piles) - index, the current player can simply take everything remaining — no need to search further moves.

Index	Limit	What happens
0	1	Alice compares taking 1 pile vs. 2 piles
1	1	Bob's turn, limit still 1 (Alice took 1)
1	2	Bob's turn, limit now 2 (if Alice had taken 2)
3	2	Only 2 piles left, 2*limit covers them — take all

Python Code

from functools import lru_cache
from typing import List


def stone_game_ii(piles: List[int]) -> int:
    n = len(piles)

    # suffix[i] = total stones from index i to the end
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]

    @lru_cache(maxsize=None)
    def best(index: int, limit: int) -> int:
        if index == n:
            return 0

        # Take-all shortcut: the whole remaining row fits in this turn
        if 2 * limit >= n - index:
            return suffix[index]

        best_score = 0
        for x in range(1, 2 * limit + 1):
            opponent_score = best(index + x, max(limit, x))
            best_score = max(best_score, suffix[index] - opponent_score)

        return best_score

    return best(0, 1)

Code Walkthrough

• suffix is built once, backward, so suffix[i] answers "how many stones remain from pile i onward" in constant time.
• best(index, limit) is the entire game in miniature: given where you are and your current limit, what's the most you can score from here on, assuming both players play optimally?
• The base case index == n means no piles are left — nothing more to score.
• The take-all shortcut avoids looping when 2*limit already covers every remaining pile — there's no strategic choice left to make.
• Otherwise, the loop tries every legal x (piles to take), recurses into the resulting state with the updated limit max(limit, x), and keeps whichever x leaves the opponent with the least favorable position for them — which is the same as leaving the most for you.
• lru_cache handles memoization automatically, keyed on (index, limit), so each state is computed exactly once.

Dry Run

Piles: [2, 7, 9, 4, 4], suffix = [26, 24, 17, 8, 4, 0].

best(0, 1): compares x = 1 and x = 2.

• x = 1: opponent gets best(1, 1), current player gets 26 - best(1, 1).
• x = 2: opponent gets best(1, 2), current player gets 26 - best(1, 2).

best(1, 2) (Bob, after Alice took 2 piles): 2*limit = 4 >= n - index = 4, take-all shortcut fires. Bob scores suffix[1] = 24. So Alice's payoff for x=2 is 26 - 24 = 2.

best(1, 1) (Bob, after Alice took 1 pile): tries x = 1 and x = 2.

• x = 2: 2*1 = 2 >= n - 1 - 2 = 2? At index 1+2=3, remaining is n - 3 = 2, and Bob's new limit is max(1,2)=2, so 2*2=4 >= 2 — take-all fires at the next level, but here we're evaluating Bob's own move. Bob taking x=2 piles (7+9=16) leaves Alice best(3, 2) = suffix[3] = 8 (take-all). Bob's payoff: 24 - 8 = 16.
• x = 1: Bob takes 1 pile (7), Alice faces best(2, 1), which recurses further and comes out to less for Bob.

Bob picks x = 2, scoring 16, leaving Alice 8 from best(1,1) = 24 - 16... — following it through, Alice's payoff for taking x=1 at the root is 26 - 16 = 10.

Comparing Alice's two options at the root: x=1 gives 10, x=2 gives 2. Alice takes 1 pile. Final result: Alice = 10, Bob = 16, matching the walkthrough.

Complexity Analysis

Time: There are at most n possible index values and n possible limit values (limit can't usefully exceed n), giving O(n^2) distinct states. Each state tries up to O(n) moves. Total: O(n^3).

Space: O(n^2) for the memoization cache (one entry per (index, limit) pair), plus O(n) for the suffix array and recursion depth.

With n capped at 100 (LeetCode's constraint), that's roughly a million operations — comfortably fast.

Alternative Solutions

Bottom-up (tabulation): Build the same dp[index][limit] table iteratively, filling it from the last pile backward instead of recursing top-down. It avoids any recursion-depth concern (irrelevant here at n ≤ 100, but relevant in languages with small stack limits), at the cost of writing the take-all shortcut and loop bounds slightly more carefully by hand. Same O(n^3) complexity — purely a style choice.

Edge Cases

• Single pile: 2 * limit trivially covers it (limit starts at 1, 2*1=2 ≥ 1), so Alice takes everything.
• All piles equal value: The algorithm doesn't special-case this — it still finds the correct optimal split based on position and limit, not pile value alone.
• Empty piles list: best(0, 1) immediately hits index == n, returning 0.
• Large limit relative to remaining piles: As soon as 2*limit reaches or exceeds what's left, the take-all shortcut fires — no further strategy to compute.
• Two equal piles ([2, 2]): Alice can only take 1 pile (limit is 1, so 2*1=2 piles would require limit ≥ 2, which she doesn't have on the first move) — she gets 2, not 4.

Common Mistakes

1. Caching by index alone, ignoring limit. Two different limits at the same index represent genuinely different game states with different outcomes.
2. Re-summing remaining piles on every call instead of precomputing suffix sums — this alone can turn an O(n^3) solution into something far slower.
3. Forgetting to update the opponent's limit, not just the index, when recursing — passing the old limit forward silently breaks the DP (a mistake called out explicitly as a real hour-long debugging session in the source explanation).
4. Treating this as a simple maximization instead of a relative-score game — not subtracting the opponent's best response leads to overcounting your own total.
5. Skipping the take-all shortcut, which isn't just an optimization — without it, some implementations mishandle the case where no further legal recursive state exists to compare against.

Interview Questions

• Why does maximizing your own score require subtracting the opponent's best score from the total, rather than just maximizing your take directly?
• How would you extend this solution if the pick limit rule were removed entirely (see Stone Game III)?
• What changes if there are three players instead of two?
• Can you convert the top-down memoized version into an iterative bottom-up table, and what ordering do you need to fill it in?
• Why is the state space O(n^2) and not O(n)?

Similar Problems

• Stone Game (LeetCode 877): The original version — fixed take-from-either-end rules, no growing limit. Good for understanding the base two-player relative-score pattern.
• Stone Game III (LeetCode 1406): Drops the growing-limit mechanic entirely; you can always take 1, 2, or 3 piles. A natural next step after mastering this problem.
• Predict the Winner (LeetCode 486): Same relative-score DP shape applied to a simpler take-from-either-end game.
• Optimal Strategy for a Game: Classic interview variant of the same alternating-turn, shrinking-resource pattern.

Key Takeaways

Stone Game II collapses into just two numbers — your position and your current limit — the Growing Window. Suffix sums turn "how much is left" into an instant lookup instead of a repeated sum. And the central lesson holds well beyond this problem: greedy grabbing loses here because your move changes your opponent's options, not just your own score. Whenever you see a two-player turn-based game, think in terms of relative score between the players, and ask whether the full game history can collapse into a small, cacheable state.

Watch the Video

Prefer to see the recursion, the suffix sums, and the full Alice-gets-10 walkthrough traced out visually? Watch the full breakdown here: {LINK}

About the Series

This walkthrough is part of Fun with Learning Technology, a series built for developers who want algorithm and systems concepts to actually click — not just get memorized. Every episode takes a problem that looks intimidating at first glance and breaks it down into the handful of ideas that make it obvious in hindsight.

Call To Action

If this helped the pattern click, drop a like on the video and subscribe on YouTube — it's the fastest way to see future breakdowns like this one. For deeper write-ups and extra problem sets, subscribe to the Substack newsletter. And if you spot a sharper way to explain any part of this, drop it in the comments — always looking to make the next one clearer.

---

def stoneGameII(piles):
    n = len(piles)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]
    memo = {}
    def dp(i, X):
        if i >= n: return 0
        if 2 * X >= n - i: return suffix[i]
        if (i, X) in memo: return memo[(i, X)]
        best = max(suffix[i] - dp(i + m, max(X, m)) for m in range(1, 2 * X + 1))
        memo[(i, X)] = best
        return best
    return dp(0, 1)