Stone Game — Solution in Python, Java & C++
Stone Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Stone Game is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Math, Game Theory
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Alice and Bob play with an even number of piles of stones arranged in a row; piles[i] is the size of the i-th pile, and the total number of stones is odd so there are no draws.
Alice goes first. On each turn a player takes the entire pile from either end of the row. The player with more stones at the end wins.
Assuming both play optimally, return true if Alice wins.
Example 1
Input: piles = [5,3,4,5]
Output: true
Example 2
Input: piles = [3,7,2,3]
Output: true
Example 3
Input: piles = [1,2]
Output: true
Constraints
2 <= piles.length <= 20piles.length is even.1 <= piles[i] <= 100The total number of stones is odd.
Hints for Stone Game
Hint 1
Define
dp[i][j]as the best score difference the player to move can force on the sub-rowi…j.Hint 2
Taking the left pile scores
piles[i]and hands the opponentdp[i+1][j], so the difference ispiles[i] - dp[i+1][j].Hint 3
Alice wins exactly when
dp[0][n-1] > 0. (Going first on an even row is in fact always a win — but prove it with the DP.)
How to solve Stone Game
dp[i][j] is the best score difference the player to move can force on piles i..j; taking an end scores that pile minus whatever the opponent can then force.
Approach
- Set
dp[i][i] = piles[i]. - For increasing lengths,
dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]). - Return
dp[0][n-1] > 0.
Why it works
Minimax on a difference collapses two players into one recurrence: the mover maximises their gain minus the opponent's optimal gain on the remainder. Alice wins iff the difference from the full row is positive.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- With an even count and odd total, the first player can always take all odd-indexed or all even-indexed piles and win — the DP proves it in general.
Reference solution
Python
def stoneGame(piles) -> bool:
n = len(piles)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = piles[i]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
return dp[0][n - 1] > 0Java
public static 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 len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] > 0;
}C++
bool stoneGame(vector<int>& piles) {
int n = (int) 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 len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] > 0;
}JavaScript
var stoneGame = function(piles) {
const n = piles.length;
const dp = [];
for (let i = 0; i < n; i++) dp.push(new Array(n).fill(0));
for (let i = 0; i < n; i++) dp[i][i] = piles[i];
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] > 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming