Stone Game II

MEDIUM✓ CHIP-TIMEDLC #1140 — FULL STATEMENT ↗

The drill: Two players alternately grab piles from the front of a row; a turn takes 1 to 2M piles where M starts at 1 and grows to match the biggest single grab so far. Both maximize their own haul — report the first player's best possible total.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A row of stone piles sits between two players who alternate turns, each grabbing some number of piles off the front of what remains — never fewer than 1 and never more than 2M, where M starts at 1 and updates as play goes on.

After any turn where a player grabs X piles, M becomes the larger of its current value and X for whoever moves next — so a big early grab widens every future turn's options. Both players are maximizing their own total stones, playing all the way to the end of the row.

The task is to report the first player's best possible total stone count, assuming both sides play optimally the whole game through.

EX 01

piles = [2, 7, 9, 4, 4]

→ 10

THE BOARD'S EXAMPLE

EX 02

piles = [1]

→ 1

MINIMUM SIZE, FORCED TAKE-ALL

EX 03

piles = [1, 1]

→ 2

TWO PILES, 2M ALREADY COVERS BOTH

pile sizes are positive integers
M starts at 1 and only ever grows as the game proceeds
a turn takes between 1 and 2M piles from the front
the answer is the first player's total stone count under optimal play

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Whatever the first player leaves behind becomes the second player's entire sub-game under the exact same rules — this is one function called on a shrinking suffix, not two separate turns to reason about.

HINT 2 THE STRUCTURE

State it as (starting index, current M): the mover at that state picks x piles between 1 and 2M, then faces the same decision from the far side of the table, with M updated to max(M, x) for whoever moves next.

HINT 3 ONE STEP FROM THE ANSWER

dp(i, M) = the suffix sum from i minus the best the opponent can do from dp(i+x, max(M,x)), maximized over legal x. Once 2M already covers everything left, there's no decision — just take it all.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE GROWING GRABPATTERN · MEMO ON (INDEX, M)piles = [2, 7, 9, 4, 4]

P1 · P2 · M

P1 → 0

P2 → 0

M → 1

STEP 1

Piles [2, 7, 9, 4, 4]. M starts at 1 — a turn may grab 1 to 2M piles from the front. P1 moves first.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/stone-game-ii.py — RACE PACE

LANG ▸

PACE ▸

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

        @functools.lru_cache(maxsize=None)
        def rec(i, m):
            if i >= n:
                return 0
            if 2 * m >= n - i:
                return suffix[i]
            best = 0
            for x in range(1, 2 * m + 1):
                if i + x > n:
                    break
                best = max(best, suffix[i] - rec(i + x, max(m, x)))
            return best

        return rec(0, 1)

TIME O(N³)SPACE O(N²)PYTHON · RACE PACE · 21 LN

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

        def rec(i, m):
            if i >= n:
                return 0
            if 2 * m >= n - i:      # this turn (or the next few) can take everything left
                return suffix[i]
            best = 0
            for x in range(1, 2 * m + 1):
                if i + x > n:
                    break
                best = max(best, suffix[i] - rec(i + x, max(m, x)))
            return best

        return rec(0, 1)

TIME O(2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 20 LN

class Solution {
    private int[] suffix;
    private int n;
    private Integer[][] memo;

    public int stoneGameII(int[] piles) {
        n = piles.length;
        suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + piles[i];
        }
        memo = new Integer[n + 1][n + 1];
        return rec(0, 1);
    }

    private int rec(int i, int m) {
        if (i >= n) return 0;
        if (2 * m >= n - i) return suffix[i];
        if (memo[i][m] != null) return memo[i][m];
        int best = 0;
        for (int x = 1; x <= 2 * m && i + x <= n; x++) {
            best = Math.max(best, suffix[i] - rec(i + x, Math.max(m, x)));
        }
        memo[i][m] = best;
        return best;
    }
}

TIME O(N³)SPACE O(N²)JAVA · RACE PACE · 27 LN

class Solution {
    private int[] suffix;
    private int n;

    public int stoneGameII(int[] piles) {
        n = piles.length;
        suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + piles[i];
        }
        return rec(0, 1);
    }

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

TIME O(2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 23 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED