Stone Game II

Medium
874.

Stone Game II

Stone Game II is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Uber interviews.

Alice and Bob take turns, Alice first. On a turn with parameter M (initially 1), the player takes all the stones from the first X remaining piles where 1 <= X <= 2M, and then M becomes max(M, X).

Both play optimally to maximise their own stones. Return the number of stones Alice ends with.

Example 1

Input
piles = [2,7,9,4,4]
Output
10
Explanation
Taking one pile first keeps the big piles reachable later.

Example 2

Input
piles = [1,2,3,4,5,100]
Output
104

Example 3

Input
piles = [1,2,3,4]
Output
5
Explanation
Alice takes the 1; Bob then forces 5 of the remaining 9, leaving Alice 4 more.

Constraints

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10000
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 {number}
 */
var stoneGameII = function(piles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Stone Game II — Solution in Python, Java & C++

Stone Game II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Stone Game II is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Uber interviews.

Problem statement

Alice and Bob take turns, Alice first. On a turn with parameter M (initially 1), the player takes all the stones from the first X remaining piles where 1 <= X <= 2M, and then M becomes max(M, X).

Both play optimally to maximise their own stones. Return the number of stones Alice ends with.

Example 1

Input: piles = [2,7,9,4,4]
Output: 10
Explanation: Taking one pile first keeps the big piles reachable later.

Example 2

Input: piles = [1,2,3,4,5,100]
Output: 104

Example 3

Input: piles = [1,2,3,4]
Output: 5
Explanation: Alice takes the 1; Bob then forces 5 of the remaining 9, leaving Alice 4 more.

Constraints

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10000

Hints for Stone Game II

  1. Hint 1

    The state is (index, M) — which piles remain and how many the mover may take.

  2. Hint 2

    Work with suffix sums: whatever the mover does not end up with goes to the opponent.

  3. Hint 3

    best(i, M) = max over X of suffix(i) - best(i + X, max(M, X)).

How to solve Stone Game II

Memoise on (i, M). The mover's total from the suffix is the whole suffix minus whatever the opponent can force from what remains — so the recurrence needs only one value per state, not two.

Approach

  1. Precompute suffix sums of piles.
  2. go(i, M): if i + 2M >= n, the mover can sweep the rest, so return suffix(i).
  3. Otherwise try every X from 1 to 2M and take the best of suffix(i) - go(i + X, max(M, X)).
  4. The answer is go(0, 1).

Why it works

The game is zero-sum over the remaining suffix: every stone left goes to one player or the other. So the mover's optimum is the suffix total minus the opponent's optimum on the smaller suffix. M never exceeds n, which bounds the state space at O(n²), and each state tries O(n) moves.

Complexity

  • Time — O(n³)
  • Space — O(n²)

Pitfalls

  • M updates to max(M, X), not to X — taking fewer piles does not shrink your future allowance.
  • The sweep base case i + 2M >= n is what stops the recursion from running off the end.
  • Tracking both players' scores separately doubles the state for no benefit.

Reference solution

Python

from functools import lru_cache
from typing import List

def stoneGameII(piles: List[int]) -> int:
    n = len(piles)
    suf = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf[i] = suf[i + 1] + piles[i]

    @lru_cache(maxsize=None)
    def go(i: int, m: int) -> int:
        if i >= n:
            return 0
        if i + 2 * m >= n:
            return suf[i]
        best = 0
        for x in range(1, 2 * m + 1):
            best = max(best, suf[i] - go(i + x, max(m, x)))
        return best

    return go(0, 1)

Java

private static int stoneGo(int i, int m, int n, int[] suf, int[][] memo) {
    if (i >= n) return 0;
    if (i + 2 * m >= n) return suf[i];
    if (memo[i][m] >= 0) return memo[i][m];
    int best = 0;
    for (int x = 1; x <= 2 * m; x++) {
        best = Math.max(best, suf[i] - stoneGo(i + x, Math.max(m, x), n, suf, memo));
    }
    memo[i][m] = best;
    return best;
}

public static int stoneGameII(int[] piles) {
    int n = piles.length;
    int[] suf = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + piles[i];
    int[][] memo = new int[n + 1][2 * n + 2];
    for (int[] row : memo) Arrays.fill(row, -1);
    return stoneGo(0, 1, n, suf, memo);
}

C++

static int stoneGo(int i, int m, int n, vector<int>& suf, vector<vector<int>>& memo) {
    if (i >= n) return 0;
    if (i + 2 * m >= n) return suf[i];
    if (memo[i][m] >= 0) return memo[i][m];
    int best = 0;
    for (int x = 1; x <= 2 * m; x++) {
        best = max(best, suf[i] - stoneGo(i + x, max(m, x), n, suf, memo));
    }
    memo[i][m] = best;
    return best;
}

int stoneGameII(vector<int>& piles) {
    int n = (int) piles.size();
    vector<int> suf(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + piles[i];
    vector<vector<int>> memo(n + 1, vector<int>(2 * n + 2, -1));
    return stoneGo(0, 1, n, suf, memo);
}

JavaScript

var stoneGameII = function(piles) {
    var n = piles.length;
    var suf = [];
    for (var t = 0; t <= n; t++) suf.push(0);
    for (var i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + piles[i];
    var memo = [];
    for (var a = 0; a <= n; a++) {
        var row = [];
        for (var b = 0; b <= 2 * n + 1; b++) row.push(-1);
        memo.push(row);
    }
    var go = function(i, m) {
        if (i >= n) return 0;
        if (i + 2 * m >= n) return suf[i];
        if (memo[i][m] >= 0) return memo[i][m];
        var best = 0;
        for (var x = 1; x <= 2 * m; x++) {
            var take = suf[i] - go(i + x, Math.max(m, x));
            if (take > best) best = take;
        }
        memo[i][m] = best;
        return best;
    };
    return go(0, 1);
};

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