Stone Game II — Medium Problem & Solution

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 <=…

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Prefix Sum, Game Theory
Asked at: Amazon, Google, Uber
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 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

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

Precompute suffix sums of piles.
go(i, M): if i + 2M >= n, the mover can sweep the rest, so return suffix(i).
Otherwise try every X from 1 to 2M and take the best of suffix(i) - go(i + X, max(M, X)).
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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue