2029. Stone Game IX | LeetCode Daily Python Solution (winner decided before move one)

Introduction

Every so often a problem shows up on LeetCode's daily list that's built to trick you into overreacting. Stone Game IX is one of those. Read it once and your brain immediately jumps to recursion, memoization, maybe a game tree with branching turn orders. That instinct is exactly what the problem is testing — not your ability to write a simulation, but your ability to notice when a simulation is unnecessary.

This matters for interviews because "two players alternate turns, who wins" is one of the most common problem shapes you'll see, and most candidates default to the same heavy machinery every time: recursion plus memoization on game state. That works until the state space explodes, and with this problem it does — fast. Learning to recognize when a two-player turn game collapses into a simple counting argument is a transferable skill that shows up far beyond this one question.

Problem Overview

Alice and Bob take turns removing stones from a pile, one at a time, with Alice always moving first. Each stone has a value. As stones get removed, the players keep a running total of everything removed so far. The instant that running total becomes divisible by 3, the player who just made that move loses immediately — the game ends right there, mid-pile if it has to.

Given the list of stone values, you need to determine: does Alice win?

Example

Take stones [2, 1].

• Alice removes 2. Running sum = 2. Not divisible by 3, game continues.
• Bob removes 1. Running sum = 3. Divisible by 3 — Bob just made this move, so Bob loses.

Alice wins.

Now take stones [2, 2]. Both stones have the same remainder when divided by 3 (remainder 2), and there are no stones with remainder 1 at all. As you'll see below, that lopsided bucket count is exactly the kind of pattern that decides the outcome before anyone touches a stone.

Intuition

The trap here is treating this as a problem about stone values. It isn't. The only thing that affects whether a running sum hits a multiple of 3 is each stone's value mod 3 — nothing else about the stone matters.

That means every stone falls into exactly one of three buckets:

• Bucket 0 — remainder 0
• Bucket 1 — remainder 1
• Bucket 2 — remainder 2

Once you see that, the entire game reduces to three integers: how many stones are in each bucket.

Think about what a remainder-0 stone does to the running sum's remainder: nothing. Adding a multiple of 3 doesn't change the sum's remainder mod 3 at all. So a remainder-0 stone is a "free" move — it consumes a turn but doesn't move anyone closer to danger.

The real tension is between remainder-1 and remainder-2 stones. Starting from a sum of 0, you're safe as long as you don't return the running total to a multiple of 3. Picking a remainder-1 stone moves you to a "1 mod 3" state; picking a remainder-2 stone moves you to "2 mod 3." From there, the next pick determines whether you land back on a multiple of 3 or not. Players are forced into an alternating pattern between the two buckets to stay safe, and whoever runs out of the "safe" bucket to pick from first is the one who eventually gets forced into a losing move.

The remainder-0 stones complicate this only in one way: since they don't change the running remainder, they effectively let a player "pass" without disturbing the 1/2 alternation — but only whoever is on move when they're used. If the count of remainder-0 stones is even, they cancel each other out in terms of who benefits. If it's odd, one of them tips the alternation in a specific direction.

Brute Force Solution

Idea: simulate the game. At each state (remaining stones, current running sum mod 3, whose turn it is), try removing each remaining stone, check if the mover loses, and recurse. Memoize on the state.

Algorithm:

1. Represent state as (count0, count1, count2, running_sum_mod_3, turn).
2. At each state, try picking from each non-empty bucket.
3. If the new running sum is divisible by 3, the current player loses.
4. Otherwise recurse into the next state with the opposite turn.
5. Alice wins if any move leads to a state where she doesn't immediately lose and Bob is forced into a loss down the line.

Advantages: correct by construction, easy to reason about for small inputs, useful if the loss condition were more complex (not a simple modulo).

Disadvantages: with up to 100,000 stones, even representing the state space explodes past anything practical. The problem constraints (up to 10^5 stones) make this approach unusable in practice — it's a correctness reference, not a real solution.

Complexity: exponential time in the naive form; even with memoization on (count0, count1, count2, sum_mod_3) it's still far too slow and memory-heavy for the input bounds, since you'd need to track exact counts alongside turn state.

Optimal Solution

Reduce the whole pile to three counters: cnt0, cnt1, cnt2 — how many stones have each remainder mod 3.

The outcome depends only on these three numbers, split into two cases based on the parity of cnt0:

Case 1: cnt0 is even. The free moves cancel out. Alice wins only if both cnt1 > 0 and cnt2 > 0. If either bucket is empty, Alice can never sustain the 1/2 alternation and loses.

Case 2: cnt0 is odd. The single leftover free move shifts the danger zone. Alice wins only if the gap between the two buckets is large enough:

abs(cnt1 - cnt2) > 2

cnt0 parity	Winning condition for Alice
even	cnt1 > 0 and cnt2 > 0
odd	abs(cnt1 - cnt2) > 2

That's the entire rule. No recursion, no memoization, no simulated turns — just a tally and one comparison.

Python Code

def stone_game_ix(stones: list[int]) -> bool:
    """Return True if Alice wins Stone Game IX."""
    cnt = [0, 0, 0]
    for stone in stones:
        cnt[stone % 3] += 1

    if cnt[0] % 2 == 0:
        return cnt[1] > 0 and cnt[2] > 0

    return abs(cnt[1] - cnt[2]) > 2

Code Walkthrough

• cnt = [0, 0, 0] — three counters, one per remainder bucket.
• for stone in stones: cnt[stone % 3] += 1 — a single pass over the input. stone % 3 gives 0, 1, or 2, and we bump the matching counter. This is the only place we touch the input list.
• if cnt[0] % 2 == 0 — checks whether the free-move (remainder-0) count is even.
• return cnt[1] > 0 and cnt[2] > 0 — in the even case, Alice needs both danger buckets populated to sustain the alternation.
• return abs(cnt[1] - cnt[2]) > 2 — in the odd case, the gap between the two buckets must exceed 2 for Alice to win. abs handles the comparison regardless of which bucket is larger.

Dry Run

Stones: [9, 7, 2, 2]

1. 9 % 3 = 0 → cnt = [1, 0, 0]
2. 7 % 3 = 1 → cnt = [1, 1, 0]
3. 2 % 3 = 2 → cnt = [1, 1, 1]
4. 2 % 3 = 2 → cnt = [1, 1, 2]

Final: cnt = [1, 1, 2].

cnt[0] = 1, which is odd → check abs(cnt[1] - cnt[2]) > 2 → abs(1 - 2) = 1, which is not greater than 2.

Result: Alice loses (Bob wins).

Complexity Analysis

• Time: O(n) — one pass over the stones to build the three counters, then constant-time arithmetic on the result. This scales cleanly to the 100,000-stone upper bound.
• Space: O(1) — exactly three counters regardless of input size, since we never need the original values again after tallying.

The correctness rests on the fact that the loss condition (running_sum % 3 == 0) depends only on the multiset of remainders, not the actual values or their order beyond which bucket they came from — which is why counting is sufficient and simulation is wasted work.

Alternative Solutions

The brute-force recursive simulation above is the only real alternative, and it's worth knowing conceptually because the same "simulate then find the counting shortcut" progression appears constantly in these problems. There's no meaningfully different optimal approach here — once you spot the mod-3 reduction, the bucket-comparison rule is essentially forced, since it's the smallest sufficient state that captures the game.

Edge Cases

• Fewer than 2 stones: with 0 stones, no move is ever made — treat this defensively depending on problem constraints (LeetCode guarantees stones.length >= 1). With 1 stone, Alice removes it; she loses only if that single stone's value is divisible by 3.
• All stones in one bucket: e.g., all remainder 2, cnt1 = 0. Alice loses regardless of cnt0's parity, since she can never start the 1/2 alternation.
• cnt0 very large, cnt1/cnt2 small: the free moves don't help Alice manufacture a win if the other buckets are empty or too close together.
• Duplicate stone values: doesn't matter — only the remainder counts matter, so duplicates just increment the same bucket.
• Maximum input size (10^5 stones): this is exactly why the O(n) bucket approach exists; brute force is not viable here.

Common Mistakes

1. Forgetting cnt0's parity flips the rule. Using the same condition regardless of whether cnt0 is even or odd is the single most common bug — it silently produces wrong answers only on odd inputs, which makes it easy to miss in testing.
2. Assuming "bigger bucket wins." It's not about which of cnt1/cnt2 is larger — it's about the size of the gap between them, measured with abs().
3. Using the wrong threshold. The odd-cnt0 case requires the gap to be strictly greater than 2, not greater than or equal to 2, and not greater than 1.
4. Trying to simulate the game directly. Writing recursive/backtracking code works on small examples but times out or exceeds memory on the real constraints (up to 100,000 stones).
5. Forgetting to check cnt1 > 0 and cnt2 > 0, not just one of them, in the even case. An empty bucket in either position breaks Alice's plan.

Interview Questions

• Why does the value of each stone not matter beyond its remainder mod 3?
• How would the rule change if the losing condition were "sum divisible by 4" instead of 3?
• Can you prove why an even count of remainder-0 stones cancels out, but an odd count doesn't?
• What's the time and space complexity of your solution, and why is brute-force simulation infeasible here?
• How would you modify this if Bob moved first instead of Alice?

Similar Problems

• Stone Game (LeetCode 877) — a related turn-based stone-removal game, but decided by optimal value selection rather than modular arithmetic.
• Nim Game (LeetCode 292) — another game where the winner is determined by a simple property of the input (divisibility) rather than simulation.
• Predict the Winner (LeetCode 486) — classic two-player game requiring DP, useful for contrasting against problems that don't reduce to a closed-form rule.
• Divisor Game (LeetCode 1025) — another mislabeled-as-hard game problem where the winner follows directly from a parity observation.

Key Takeaways

Stone Game IX teaches a pattern that's bigger than the problem itself: when you see a two-player turn-based game, resist the urge to model every move. Ask what minimal state actually determines the outcome. Here, that state was three integers — remainder-bucket counts — and one parity check. Recognizing this kind of reduction is what separates a brute-force answer from an O(n) one, and it's exactly the kind of judgment interviewers are probing for.

Watch the Video

For the full visual walkthrough — including the bucket trace, the brute-force comparison, and two live quiz rounds — watch the video here: {LINK}

About the Series

This breakdown is part of Fun with Learning Technology, a series dedicated to making LeetCode problems, algorithms, and core computer science concepts genuinely click — not just memorized, but understood well enough to reconstruct under interview pressure.

Call To Action

If this explanation helped the mod-3 trick finally make sense, leave a like on the video and subscribe for more daily LeetCode breakdowns. For deeper dives and bonus problem sets, subscribe to the Substack newsletter. Drop your questions or problem requests in the comments, and share this with anyone prepping for coding interviews.

---

def stoneGameIX(stones):
    cnt = [0, 0, 0]
    for s in stones:
        cnt[s % 3] += 1
    if cnt[0] % 2 == 0:
        return cnt[1] >= 1 and cnt[2] >= 1
    return abs(cnt[1] - cnt[2]) > 2