Stone Game III
Description
Alice and Bob are playing a game with a row of stones. Each stone has an integer value, which can be positive, negative, or zero, given in the array stoneValue.
The rules of the game are:
- Alice and Bob take turns, with Alice going first.
- On each turn, the current player must take exactly 1, 2, or 3 stones from the beginning of the remaining row.
- Each player's score is the sum of the values of all stones they have taken. Both players start with a score of 0.
- The game ends when all stones have been taken.
- Both players play optimally, meaning each player makes the move that maximizes their own advantage.
Return "Alice" if Alice ends with a strictly higher score than Bob, "Bob" if Bob ends with a strictly higher score, or "Tie" if both players end with the same score.
The twist that makes this problem interesting is the presence of negative values — sometimes a player might want to force the opponent to pick up negative-valued stones by carefully choosing how many stones to take.
Examples
Example 1
Input: stoneValue = [1, 2, 3, 7]
Output: "Bob"
Explanation: No matter what Alice does, Bob wins. If Alice takes 1 stone (value 1), Bob takes the remaining 3 stones (values 2+3+7=12), so scores are Alice=1, Bob=12. If Alice takes 2 stones (values 1+2=3), Bob takes 2 stones (values 3+7=10), scores are Alice=3, Bob=10. If Alice takes 3 stones (values 1+2+3=6), Bob takes the last stone (value 7), scores are Alice=6, Bob=7. In every case, Bob has a higher score.
Example 2
Input: stoneValue = [1, 2, 3, -9]
Output: "Alice"
Explanation: Alice's optimal strategy is to take all three stones at once (values 1+2+3=6). This forces Bob to take the last stone with value -9, giving Bob a score of -9. Final scores: Alice=6, Bob=-9. Alice wins by 15 points. If Alice took fewer stones initially, Bob could play in a way that gives him a better outcome.
Example 3
Input: stoneValue = [1, 2, 3, 6]
Output: "Tie"
Explanation: If Alice takes all three stones first (values 1+2+3=6), Bob takes the last stone (value 6). Both end with score 6, resulting in a tie. This is Alice's best strategy — any other choice would let Bob win.
Constraints
- 1 ≤ stoneValue.length ≤ 5 × 10^4
- -1000 ≤ stoneValue[i] ≤ 1000
Editorial
Brute Force
Intuition
The most straightforward way to solve this problem is to simulate every possible game scenario. At each turn, the current player has three choices: take 1, 2, or 3 stones. Since both players play optimally, each player will pick the option that maximizes their own advantage.
We can think of this using a concept called score difference. Instead of tracking Alice's and Bob's scores separately, we track the difference from the current player's perspective. If it's your turn starting at position i, define dfs(i) as the maximum score advantage you can achieve over your opponent from this point onward.
Why does score difference work? When you take some stones, their values add to your score. Then your opponent plays optimally from the remaining position, achieving their own best score difference. Since your opponent's gain is your loss, you subtract their result.
So: dfs(i) = max over taking 1, 2, or 3 stones of (sum of stones taken - dfs(next position))
If dfs(0) > 0, Alice (the first player) wins. If dfs(0) < 0, Bob wins. If dfs(0) = 0, it's a tie.
Without any caching, this recursion explores every possible sequence of moves, branching into 3 choices at each level, leading to exponential time.
Step-by-Step Explanation
Let's trace through with stoneValue = [1, 2, 3, -9]:
Step 1: Call dfs(0). Alice starts. She can take 1, 2, or 3 stones.
Step 2: Option A — Alice takes 1 stone (value 1). Score gain = 1. Bob plays from index 1. Alice's advantage = 1 - dfs(1).
Step 3: We need dfs(1). Bob starts from [2, 3, -9]. Bob can take 1, 2, or 3 stones.
- Take 1 (value 2): advantage = 2 - dfs(2)
- Take 2 (values 2+3=5): advantage = 5 - dfs(3)
- Take 3 (values 2+3+(-9)=-4): advantage = -4 - dfs(4) = -4 - 0 = -4
Step 4: We need dfs(2). Current player starts from [3, -9].
- Take 1 (value 3): advantage = 3 - dfs(3)
- Take 2 (values 3+(-9)=-6): advantage = -6 - dfs(4) = -6 - 0 = -6
Step 5: We need dfs(3). Current player starts from [-9].
- Take 1 (value -9): advantage = -9 - dfs(4) = -9 - 0 = -9
- dfs(3) = -9
Step 6: Back to dfs(2): Take 1 → 3 - (-9) = 12. Take 2 → -6. dfs(2) = 12.
Step 7: Back to dfs(1): Take 1 → 2 - 12 = -10. Take 2 → 5 - (-9) = 14. Take 3 → -4. dfs(1) = 14.
Step 8: Back to dfs(0), Option A: 1 - 14 = -13.
Step 9: Option B — Alice takes 2 stones (values 1+2=3). Advantage = 3 - dfs(2) = 3 - 12 = -9.
Step 10: Option C — Alice takes 3 stones (values 1+2+3=6). Advantage = 6 - dfs(3) = 6 - (-9) = 15.
Step 11: dfs(0) = max(-13, -9, 15) = 15. Since 15 > 0, Alice wins!
Stone Game III — Recursive Score Difference for [1, 2, 3, -9] — Watch how the recursion explores all possible move sequences, computing the score difference at each node. Each player picks the option maximizing their own advantage.
Algorithm
- Define dfs(i) = maximum score difference the current player can achieve starting from index i
- Base case: if i ≥ n, return 0 (no stones left)
- For each choice of taking 1, 2, or 3 stones:
- Compute the sum of stones taken
- Score difference = sum_taken - dfs(i + num_taken)
- Track the maximum
- Return the maximum score difference
- If dfs(0) > 0, return "Alice"; if < 0, return "Bob"; if == 0, return "Tie"
Code
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
// Pure recursion without memoization
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) return 0;
int best = INT_MIN;
int sum = 0;
for (int k = 0; k < 3 && i + k < n; k++) {
sum += stoneValue[i + k];
best = max(best, sum - dfs(i + k + 1));
}
return best;
};
int result = dfs(0);
if (result > 0) return "Alice";
if (result < 0) return "Bob";
return "Tie";
}
};class Solution:
def stoneGameIII(self, stoneValue: list[int]) -> str:
n = len(stoneValue)
# Pure recursion without memoization
def dfs(i: int) -> int:
if i >= n:
return 0
best = float('-inf')
total = 0
for k in range(3):
if i + k >= n:
break
total += stoneValue[i + k]
best = max(best, total - dfs(i + k + 1))
return best
result = dfs(0)
if result > 0:
return "Alice"
elif result < 0:
return "Bob"
else:
return "Tie"class Solution {
private int[] stoneValue;
private int n;
public String stoneGameIII(int[] stoneValue) {
this.stoneValue = stoneValue;
this.n = stoneValue.length;
int result = dfs(0);
if (result > 0) return "Alice";
if (result < 0) return "Bob";
return "Tie";
}
private int dfs(int i) {
if (i >= n) return 0;
int best = Integer.MIN_VALUE;
int sum = 0;
for (int k = 0; k < 3 && i + k < n; k++) {
sum += stoneValue[i + k];
best = Math.max(best, sum - dfs(i + k + 1));
}
return best;
}
}Complexity Analysis
Time Complexity: O(3ⁿ)
At each position, the recursion branches into up to 3 sub-calls (take 1, 2, or 3 stones). Without memoization, the same subproblems are solved repeatedly. The recursion tree has depth n (worst case, taking 1 stone each time) and branching factor 3, yielding O(3ⁿ) total calls.
Space Complexity: O(n)
The maximum recursion depth is n (when each recursive call takes only 1 stone), so the call stack uses O(n) space.
Why This Approach Is Not Efficient
The brute force recursion has O(3ⁿ) time complexity, which is catastrophically slow for the given constraint of n up to 50,000. Even for n = 30, 3³⁰ ≈ 2 × 10¹⁴ — far beyond what can be computed in time.
The root cause is overlapping subproblems. The same dfs(i) gets computed many times from different paths. For example, dfs(5) might be called when the parent took 1 stone from position 4, or 2 stones from position 3, or 3 stones from position 2. Each of these paths triggers a fresh computation of dfs(5) and all its descendants.
Since dfs(i) depends only on the starting index i (not on who took what before), we can cache each result and look it up instead of recomputing. This transforms the exponential recursion into an O(n) solution — each of the n states is computed exactly once.
Better Approach - Memoized Recursion (Top-Down DP)
Intuition
The key observation is that the result of dfs(i) — the maximum score difference achievable starting from position i — depends only on i, not on the history of moves that led to position i. This means there are only n distinct subproblems (positions 0 through n-1), yet the brute force recursion solves many of them multiple times.
By adding a cache (memoization table), we store the result of dfs(i) the first time it is computed. On subsequent calls to dfs(i), we simply return the cached value in O(1) time. This transforms the time complexity from O(3ⁿ) to O(n), since each of the n states is computed exactly once, and each computation does at most 3 iterations of constant work.
The recursion remains the same — dfs(i) = max over taking 1, 2, or 3 stones of (sum taken - dfs(next)) — but now with a lookup table eliminating redundant work.
This approach naturally preserves the elegant recursive structure while being efficient enough for n up to 50,000.
Step-by-Step Explanation
Let's trace through with stoneValue = [1, 2, 3, 7] using memoized recursion:
Step 1: Call dfs(0). Not in cache. Alice starts with [1, 2, 3, 7].
Step 2: For dfs(0), we need dfs(1), dfs(2), dfs(3). Let's compute bottom-up.
Step 3: dfs(4) = 0 (base case, no stones left). Cache: {4: 0}.
Step 4: dfs(3): Only stone [7] remains. Take 1 → 7 - dfs(4) = 7 - 0 = 7. dfs(3) = 7. Cache: {4: 0, 3: 7}.
Step 5: dfs(2): Stones [3, 7]. Take 1 → 3 - dfs(3) = 3 - 7 = -4. Take 2 → (3+7) - dfs(4) = 10 - 0 = 10. dfs(2) = max(-4, 10) = 10. Cache: {4: 0, 3: 7, 2: 10}.
Step 6: dfs(1): Stones [2, 3, 7]. Take 1 → 2 - dfs(2) = 2 - 10 = -8. Take 2 → (2+3) - dfs(3) = 5 - 7 = -2. Take 3 → (2+3+7) - dfs(4) = 12 - 0 = 12. dfs(1) = max(-8, -2, 12) = 12. Cache: {4: 0, 3: 7, 2: 10, 1: 12}.
Step 7: dfs(0): Stones [1, 2, 3, 7]. Take 1 → 1 - dfs(1) = 1 - 12 = -11. Take 2 → (1+2) - dfs(2) = 3 - 10 = -7. Take 3 → (1+2+3) - dfs(3) = 6 - 7 = -1. dfs(0) = max(-11, -7, -1) = -1.
Step 8: dfs(0) = -1 < 0. Bob wins! Alice's best strategy only loses by 1 point.
Stone Game III — Memoized DP Table for [1, 2, 3, 7] — Watch how the memo cache fills from right to left, with each entry computed once using at most 3 lookups into already-cached values.
Algorithm
- Create a cache/memo dictionary to store computed dfs results
- Define dfs(i) with memoization:
- Base case: if i ≥ n, return 0
- If i is in cache, return cached value
- For k = 0, 1, 2 (taking k+1 stones):
- Accumulate sum of stones[i..i+k]
- Compute advantage = sum - dfs(i + k + 1)
- Track maximum advantage
- Store and return the maximum
- Compute dfs(0) and determine winner based on sign
Code
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
vector<int> memo(n, INT_MIN);
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) return 0;
if (memo[i] != INT_MIN) return memo[i];
int best = INT_MIN;
int sum = 0;
for (int k = 0; k < 3 && i + k < n; k++) {
sum += stoneValue[i + k];
best = max(best, sum - dfs(i + k + 1));
}
return memo[i] = best;
};
int result = dfs(0);
if (result > 0) return "Alice";
if (result < 0) return "Bob";
return "Tie";
}
};from functools import cache
class Solution:
def stoneGameIII(self, stoneValue: list[int]) -> str:
n = len(stoneValue)
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
best = float('-inf')
total = 0
for k in range(3):
if i + k >= n:
break
total += stoneValue[i + k]
best = max(best, total - dfs(i + k + 1))
return best
result = dfs(0)
if result > 0:
return "Alice"
elif result < 0:
return "Bob"
else:
return "Tie"class Solution {
private int[] stoneValue;
private int n;
private Integer[] memo;
public String stoneGameIII(int[] stoneValue) {
this.stoneValue = stoneValue;
this.n = stoneValue.length;
this.memo = new Integer[n];
int result = dfs(0);
if (result > 0) return "Alice";
if (result < 0) return "Bob";
return "Tie";
}
private int dfs(int i) {
if (i >= n) return 0;
if (memo[i] != null) return memo[i];
int best = Integer.MIN_VALUE;
int sum = 0;
for (int k = 0; k < 3 && i + k < n; k++) {
sum += stoneValue[i + k];
best = Math.max(best, sum - dfs(i + k + 1));
}
return memo[i] = best;
}
}Complexity Analysis
Time Complexity: O(n)
There are n unique states (dfs(0) through dfs(n-1)). Each state is computed exactly once due to memoization. For each state, we do at most 3 iterations of constant work (sum, subtract, compare). Total: n × 3 = O(n).
Space Complexity: O(n)
The memoization cache stores n entries, each using O(1) space. The recursion call stack has maximum depth n (in the worst case, each call takes 1 stone). Total space: O(n) for cache + O(n) for stack = O(n).
Why This Approach Is Not Efficient
The memoized recursion is already O(n) in time, which is optimal for this problem since we must examine each stone at least once. However, there are two practical concerns:
-
Recursion stack depth: With n up to 50,000, the recursive approach can hit Python's default recursion limit or cause stack overflow in languages with limited stack size. The worst case occurs when the recursion chain is dfs(0) → dfs(1) → dfs(2) → ... → dfs(n), requiring O(n) stack frames.
-
Overhead of function calls: Each memoized recursive call has overhead from the function call mechanism, cache lookup, and stack frame management. For n = 50,000, this overhead is noticeable.
We can eliminate both issues by converting to a bottom-up iterative approach. Furthermore, since dfs(i) only depends on dfs(i+1), dfs(i+2), and dfs(i+3) — just the next 3 values — we can reduce space from O(n) to O(1) by keeping only 3 variables instead of the full array.
Optimal Approach - Bottom-Up DP with Space Optimization
Intuition
Instead of computing dfs values top-down with recursion, we can fill a DP table iterating from right to left (from the end of the array to the beginning). This is a direct translation of the recursive solution into an iterative one.
Define dp[i] as the maximum score difference the current player can achieve starting from index i. The recurrence is:
dp[i] = max over j=1,2,3 of (sum of stoneValue[i..i+j-1] - dp[i+j])
with dp[n] = dp[n+1] = dp[n+2] = 0 (base cases for when no stones remain).
The critical space optimization insight: dp[i] depends ONLY on dp[i+1], dp[i+2], and dp[i+3]. We don't need the entire array — just the three most recently computed values. We can use a rolling window of 3 variables, bringing space from O(n) down to O(1).
This eliminates recursion entirely (no stack overflow risk) and minimizes memory usage, making it the most efficient solution for this problem.
Step-by-Step Explanation
Let's trace through with stoneValue = [1, 2, 3, 7] using bottom-up DP:
Step 1: Initialize dp[4] = dp[5] = dp[6] = 0 (base cases: positions beyond the array).
Step 2: Compute dp[3] (stones from index 3 onward: [7]):
- Take 1 stone: sum=7, advantage = 7 - dp[4] = 7 - 0 = 7
- dp[3] = 7
Step 3: Compute dp[2] (stones from index 2 onward: [3, 7]):
- Take 1: sum=3, advantage = 3 - dp[3] = 3 - 7 = -4
- Take 2: sum=3+7=10, advantage = 10 - dp[4] = 10 - 0 = 10
- dp[2] = max(-4, 10) = 10
Step 4: Compute dp[1] (stones from index 1 onward: [2, 3, 7]):
- Take 1: sum=2, advantage = 2 - dp[2] = 2 - 10 = -8
- Take 2: sum=2+3=5, advantage = 5 - dp[3] = 5 - 7 = -2
- Take 3: sum=2+3+7=12, advantage = 12 - dp[4] = 12 - 0 = 12
- dp[1] = max(-8, -2, 12) = 12
Step 5: Compute dp[0] (all stones: [1, 2, 3, 7]):
- Take 1: sum=1, advantage = 1 - dp[1] = 1 - 12 = -11
- Take 2: sum=1+2=3, advantage = 3 - dp[2] = 3 - 10 = -7
- Take 3: sum=1+2+3=6, advantage = 6 - dp[3] = 6 - 7 = -1
- dp[0] = max(-11, -7, -1) = -1
Step 6: dp[0] = -1 < 0 → Bob wins!
Stone Game III — Bottom-Up DP for [1, 2, 3, 7] — Watch the DP table fill from right to left. Each cell represents the best score difference the current player can achieve from that position. Only 3 previous values are needed at each step.
Algorithm
Full DP Array Version:
- Create dp array of size n+3, initialized to 0
- Iterate i from n-1 down to 0:
- Initialize best = -infinity, sum = 0
- For k = 0, 1, 2 (taking k+1 stones):
- If i + k < n: sum += stoneValue[i + k]
- best = max(best, sum - dp[i + k + 1])
- dp[i] = best
- If dp[0] > 0, return "Alice"; if dp[0] < 0, return "Bob"; else return "Tie"
Space-Optimized Version (O(1) space):
- Maintain only 3 variables: dp_i1, dp_i2, dp_i3 (representing dp[i+1], dp[i+2], dp[i+3])
- Iterate i from n-1 down to 0, computing dp[i] using only these 3 values
- After each iteration, shift the window: dp_i3 = dp_i2, dp_i2 = dp_i1, dp_i1 = dp[i]
Code
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
// Space-optimized: only need 3 future values
// dp_i1 = dp[i+1], dp_i2 = dp[i+2], dp_i3 = dp[i+3]
int dp_i1 = 0, dp_i2 = 0, dp_i3 = 0;
for (int i = n - 1; i >= 0; i--) {
int best = INT_MIN;
int sum = 0;
int future[3] = {dp_i1, dp_i2, dp_i3};
for (int k = 0; k < 3 && i + k < n; k++) {
sum += stoneValue[i + k];
best = max(best, sum - future[k]);
}
// Shift window
dp_i3 = dp_i2;
dp_i2 = dp_i1;
dp_i1 = best;
}
if (dp_i1 > 0) return "Alice";
if (dp_i1 < 0) return "Bob";
return "Tie";
}
};class Solution:
def stoneGameIII(self, stoneValue: list[int]) -> str:
n = len(stoneValue)
# Space-optimized: only need 3 future values
# dp_i1 = dp[i+1], dp_i2 = dp[i+2], dp_i3 = dp[i+3]
dp_i1, dp_i2, dp_i3 = 0, 0, 0
for i in range(n - 1, -1, -1):
best = float('-inf')
total = 0
future = [dp_i1, dp_i2, dp_i3]
for k in range(3):
if i + k >= n:
break
total += stoneValue[i + k]
best = max(best, total - future[k])
# Shift window
dp_i3 = dp_i2
dp_i2 = dp_i1
dp_i1 = best
if dp_i1 > 0:
return "Alice"
elif dp_i1 < 0:
return "Bob"
else:
return "Tie"class Solution {
public String stoneGameIII(int[] stoneValue) {
int n = stoneValue.length;
// Space-optimized: only need 3 future values
int dpI1 = 0, dpI2 = 0, dpI3 = 0;
for (int i = n - 1; i >= 0; i--) {
int best = Integer.MIN_VALUE;
int sum = 0;
int[] future = {dpI1, dpI2, dpI3};
for (int k = 0; k < 3 && i + k < n; k++) {
sum += stoneValue[i + k];
best = Math.max(best, sum - future[k]);
}
// Shift window
dpI3 = dpI2;
dpI2 = dpI1;
dpI1 = best;
}
if (dpI1 > 0) return "Alice";
if (dpI1 < 0) return "Bob";
return "Tie";
}
}Complexity Analysis
Time Complexity: O(n)
We iterate once from i = n-1 down to 0. For each position, we do at most 3 iterations of constant work (adding a stone value, computing advantage, comparing). Total: n × 3 = O(n). This is optimal since we must read each stone value at least once.
Space Complexity: O(1)
We use only 3 integer variables (dp_i1, dp_i2, dp_i3) plus a few loop variables. No arrays, no recursion stack, no hash maps. The space does not grow with input size.
Compared to the memoized approach (O(n) space for cache + recursion stack), this is a significant improvement, especially for n up to 50,000. It also eliminates the risk of stack overflow from deep recursion.