Stone Game

Medium
326.

Stone Game

Stone Game is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Adobe interviews.

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 <= 20
  • piles.length is even.
  • 1 <= piles[i] <= 100
  • The total number of stones is odd.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} piles
 * @return {boolean}
 */
var stoneGame = function(piles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 20
  • piles.length is even.
  • 1 <= piles[i] <= 100
  • The total number of stones is odd.

Hints for Stone Game

  1. Hint 1

    Define dp[i][j] as the best score difference the player to move can force on the sub-row i…j.

  2. Hint 2

    Taking the left pile scores piles[i] and hands the opponent dp[i+1][j], so the difference is piles[i] - dp[i+1][j].

  3. 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

  1. Set dp[i][i] = piles[i].
  2. For increasing lengths, dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]).
  3. 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] > 0

Java

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