Stone Game IX solution and explanation
4 more videos on this problem
2029. Stone Game IX (Leetcode Medium)Programming Live with Larry · 38:19 · 1K views
【每日一题】LeetCode 2029. Stone Game IX 10/11/2021Huifeng Guan · 24:24 · 778 views
Leetcode 2029. Stone Game IX (construct alice win cases)LetsCode · 20:27 · 398 views
Final Stone Game IX! Leetcode Weekly Contest 261 (64th) with commentaryProgramming Live with Larry · 59:36 · 302 views
LeetCode 2029: Stone Game IXAlitaCode · 24:56 · 24 views
The problem
Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.
Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice's turn).
Assuming both players play optimally, return true if Alice wins and false if Bob wins.
Example 1:
Input: stones = [2,1] Output: true Explanation: The game will be played as follows: - Turn 1: Alice can remove either stone. - Turn 2: Bob removes the remaining stone. The sum of the removed stones is 1 + 2 = 3 and is divisible by 3. Therefore, Bob loses and Alice wins the game.
Example 2:
Input: stones = [2] Output: false Explanation: Alice will remove the only stone, and the sum of the values on the removed stones is 2. Since all the stones are removed and the sum of values is not divisible by 3, Bob wins the game.
Example 3:
Input: stones = [5,1,2,4,3] Output: false Explanation: Bob will always win. One possible way for Bob to win is shown below: - Turn 1: Alice can remove the second stone with value 1. Sum of removed stones = 1. - Turn 2: Bob removes the fifth stone with value 3. Sum of removed stones = 1 + 3 = 4. - Turn 3: Alices removes the fourth stone with value 4. Sum of removed stones = 1 + 3 + 4 = 8. - Turn 4: Bob removes the third stone with value 2. Sum of removed stones = 1 + 3 + 4 + 2 = 10. - Turn 5: Alice removes the first stone with value 5. Sum of removed stones = 1 + 3 + 4 + 2 + 5 = 15. Alice loses the game because the sum of the removed stones (15) is divisible by 3. Bob wins the game.
Constraints:
1 <= stones.length <= 1051 <= stones[i] <= 104
Approach overview
Problem Overview: You are given an array of stones where each value contributes to a running sum. Players alternately remove a stone, and if the total sum becomes divisible by 3, the player who made that move loses. Alice starts first. The goal is to determine whether Alice can guarantee a win assuming both players play optimally.
Approach 1: Simulated Play with Greedy Heuristic (O(n) time, O(1) space)
The game depends only on the remainder of each stone modulo 3. First count how many stones produce remainders 0, 1, and 2. During simulation, players avoid moves that make the running sum divisible by 3. Greedy selection prefers stones that keep the sum in a safe state while forcing the opponent into a losing move. Stones with remainder 0 do not change the sum modulo but flip the turn pressure, which creates alternating traps. By simulating decisions using the counts of each remainder group, you approximate optimal play without exploring every game branch.
Approach 2: Modulo Counting Strategy (O(n) time, O(1) space)
The key insight is that only the remainder of each stone modulo 3 matters. Compute counts c0, c1, and c2 where stone % 3 equals 0, 1, or 2. Stones with remainder 0 keep the sum unchanged but swap the advantage between players. The outcome depends on how many remainder-1 and remainder-2 stones exist relative to each other. If c0 is even, Alice wins only when both c1 and c2 are non‑zero. If c0 is odd, the difference between c1 and c2 must exceed 2 for Alice to win. This reasoning collapses the entire game tree into a few arithmetic conditions derived from remainder counts.
The solution relies heavily on counting frequencies and understanding the modular behavior of the running sum. The decision logic is essentially a compact form of game theory, where each move attempts to push the opponent into a forced losing state. The input itself is processed using a simple array traversal.
Recommended for interviews: The modulo counting strategy is what interviewers expect. It demonstrates that you recognized the invariant created by sum % 3 and reduced the entire game to three counters and a few conditional checks. Explaining the greedy simulation first can show understanding of the gameplay mechanics, but the counting approach proves you can compress a game-theory problem into an O(n) pass with constant space.
Approach 1: Modulo Counting Strategy
In this approach, the key is to utilize modulo 3 operations, as the sum's divisibility by 3 determines the game outcome. Count the stones of type 0, 1, and 2 based on their values modulo 3. Our strategy revolves around these types to determine the moves for both players. Simply analyzing number parity and the effect of moves will help us conclude the result in constant time complexity.
def stoneGameIX(stones):
count = [0, 0, 0]
for stone in stones:
count[stone % 3] += 1
if count[0] % 2 == 0:
return count[1] >= 1 and count[2] >= 1
return abs(count[1] - count[2]) > 2class Solution {
public boolean stoneGameIX(int[] stones) {
int[] count = new int[3];
for (int stone : stones) {
count[stone % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return Math.abs(count[1] - count[2]) > 2;
}
}#include <vector>
using namespace std;
bool stoneGameIX(vector<int>& stones) {
int count[3] = {0};
for (int stone : stones) {
count[stone % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return abs(count[1] - count[2]) > 2;
}function stoneGameIX(stones) {
let count = [0, 0, 0];
for (let stone of stones) {
count[stone % 3]++;
}
if (count[0] % 2 === 0) {
return count[1] >= 1 && count[2] >= 1;
}
return Math.abs(count[1] - count[2]) > 2;
}#include <stdbool.h>
bool stoneGameIX(int* stones, int stonesSize) {
int count[3] = {0};
for (int i = 0; i < stonesSize; ++i) {
count[stones[i] % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return abs(count[1] - count[2]) > 2;
}public class Solution {
public bool StoneGameIX(int[] stones) {
int[] count = new int[3];
foreach (int stone in stones) {
count[stone % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return Math.Abs(count[1] - count[2]) > 2;
}
}By counting stones and analyzing the differences and counts based on modulo 3, the solution derives a win/loss condition for Alice.
Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Simulated Play with Greedy Heuristic
This approach considers playing out a few scenarios following a simulated game sequence. Instead of brute forcing all possibilities, we use a greedy heuristic on types 1 and 2 to evaluate the game's progress. This approach is less efficient in space usage but can illuminate tactical strengths in specific board states.
def stoneGameIX(stones):
count = [0, 0, 0]
for stone in stones:
count[stone % 3] += 1
if count[0] % 2 == 0:
return count[1] >= 1 and count[2] >= 1
return abs(count[1] - count[2]) > 2class Solution {
public boolean stoneGameIX(int[] stones) {
int[] count = new int[3];
for (int stone : stones) {
count[stone % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return Math.abs(count[1] - count[2]) > 2;
}
}#include <vector>
using namespace std;
bool stoneGameIX(vector<int>& stones) {
int count[3] = {0};
for (int stone : stones) {
count[stone % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return abs(count[1] - count[2]) > 2;
}function stoneGameIX(stones) {
let count = [0, 0, 0];
for (let stone of stones) {
count[stone % 3]++;
}
if (count[0] % 2 === 0) {
return count[1] >= 1 && count[2] >= 1;
}
return Math.abs(count[1] - count[2]) > 2;
}#include <stdbool.h>
#include <stdlib.h>
bool stoneGameIX(int* stones, int stonesSize) {
int count[3] = {0};
for (int i = 0; i < stonesSize; ++i) {
count[stones[i] % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return abs(count[1] - count[2]) > 2;
}public class Solution {
public bool StoneGameIX(int[] stones) {
int[] count = new int[3];
foreach (int stone in stones) {
count[stone % 3]++;
}
if (count[0] % 2 == 0) {
return count[1] >= 1 && count[2] >= 1;
}
return Math.Abs(count[1] - count[2]) > 2;
}
}This approach involves strategically simulating a decision tree with greed to check potential Bob losses and wins for Alice, and adapts to stone counts dynamically.
Time Complexity: O(n). Space Complexity: O(1).
Approach 3: Greedy + Case Discussion
Since the player's goal is to ensure the total value of the removed stones is not divisible by 3, we only need to consider the remainder of each stone's value when divided by 3.
We use an array cnt of length 3 to maintain the count of the current remaining stones' values modulo 3, where cnt[0] represents the count of stones with a remainder of 0, and cnt[1] and cnt[2] respectively represent the counts of stones with remainders of 1 and 2.
In the first round, Alice cannot remove stones with a remainder of 0, as this would make the total value of the removed stones divisible by 3. Therefore, Alice can only remove stones with a remainder of 1 or 2.
First, let's consider the case where Alice removes a stone with a remainder of 1. If Alice removes a stone with a remainder of 1, the remainder of the total value of stones 0 against 3 will not change, so stones with a value remainder of 0 can be removed in any round, which we will not consider for now. Thus, Bob can only remove stones with a remainder of 1, followed by Alice removing stones with a remainder of 2, and so on, in the sequence 1, 1, 2, 1, 2, ldots. In this scenario, if the final round is odd and there are still remaining stones, then Alice wins; otherwise, Bob wins.
For the case where Alice removes a stone with a remainder of 2 in the first round, we can draw a similar conclusion.
The time complexity is O(n), where n is the length of the array stones. The space complexity is O(1).
function stoneGameIX(stones: number[]): boolean {
const c1: number[] = Array(3).fill(0);
for (const x of stones) {
++c1[x % 3];
}
const c2: number[] = [c1[0], c1[2], c1[1]];
const check = (cnt: number[]): boolean => {
if (--cnt[1] < 0) {
return false;
}
let r = 1 + Math.min(cnt[1], cnt[2]) * 2 + cnt[0];
if (cnt[1] > cnt[2]) {
--cnt[1];
++r;
}
return r % 2 === 1 && cnt[1] !== cnt[2];
};
return check(c1) || check(c2);
}func stoneGameIX(stones []int) bool {
c1 := [3]int{}
for _, x := range stones {
c1[x%3]++
}
c2 := [3]int{c1[0], c1[2], c1[1]}
check := func(cnt [3]int) bool {
if cnt[1] == 0 {
return false
}
cnt[1]--
r := 1 + min(cnt[1], cnt[2])*2 + cnt[0]
if cnt[1] > cnt[2] {
cnt[1]--
r++
}
return r%2 == 1 && cnt[1] != cnt[2]
}
return check(c1) || check(c2)
}Approach 4: Simulation
function stoneGameIX(stones: number[]): boolean {
if (stones.length === 1) return false;
const cnt = Array(3).fill(0);
for (const x of stones) cnt[x % 3]++;
const check = (x: number, cnt: number[]): boolean => {
let c = 1;
if (--cnt[x] < 0) return false;
while (cnt[1] || cnt[2]) {
if (cnt[x]) {
cnt[x]--;
x = x === 1 ? 2 : 1;
} else return (c + cnt[0]) % 2 === 1;
c++;
}
return false;
};
return check(1, [...cnt]) || check(2, [...cnt]);
}Complexity comparison
| Approach | Complexity |
|---|---|
| Modulo Counting Strategy | Time Complexity: O(n). Space Complexity: O(1). |
| Simulated Play with Greedy Heuristic | Time Complexity: O(n). Space Complexity: O(1). |
| Greedy + Case Discussion | – |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulated Play with Greedy Heuristic | O(n) | O(1) | Useful to reason about gameplay mechanics and understand how moves affect the running sum modulo 3. |
| Modulo Counting Strategy | O(n) | O(1) | Best approach for interviews and production solutions. Converts the game into simple remainder counts and deterministic conditions. |
Frequently asked questions
Is Stone Game IX easy or hard?
Stone Game IX is rated Medium because the implementation is simple but the insight is not obvious. Recognizing that the game depends only on sum % 3 and reducing the problem to remainder counts requires modular arithmetic and game-theory reasoning.
Stone Game IX Python/Java solution
Python, Java, C++, C#, and JavaScript implementations all follow the same logic: count stones by remainder modulo 3 and apply the winning conditions derived from those counts. Because the algorithm uses only a single pass and constant memory, the code remains short and efficient in every language.
How to solve Stone Game IX in O(n)?
Traverse the array and count stones where value % 3 equals 0, 1, or 2. The winner depends on these counts: if the count of remainder-0 stones is even, both remainder-1 and remainder-2 groups must exist for Alice to win. If it is odd, the absolute difference between the counts of remainder-1 and remainder-2 must be greater than two.
What is the best approach for Stone Game IX?
The modulo counting strategy is the optimal approach. Count stones by their remainder when divided by 3 (0, 1, 2) and apply game rules based on these counts. This reduces the entire decision to a few conditional checks while running in O(n) time and O(1) space.
Is Stone Game IX asked at Google/Amazon/Meta?
Stone Game IX represents the type of modular arithmetic and game-theory reasoning commonly asked in interviews at companies like Google, Amazon, and Meta. Variants of stone games and optimal play problems frequently appear in technical interviews.
What data structure is used in Stone Game IX?
The solution primarily uses simple counters stored in variables or a small array of size three. These counters track frequencies of stones by remainder modulo 3, making the approach a combination of array traversal and counting.
What is the time complexity of Stone Game IX?
The optimal solution runs in O(n) time because the array is scanned once to count how many stones fall into each remainder category modulo 3. The final decision uses constant-time conditions, and the space complexity remains O(1).