Stone Game

MEDIUM✓ CHIP-TIMEDLC #877 — FULL STATEMENT ↗

The drill: Two players alternate taking a whole pile from either end of a row of stone piles, each trying to end up with more stones than the other. Determine whether the player who moves first can force a win.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A row of stone piles sits between two players who alternate turns, each taking one whole pile from either end of whatever remains — never from the middle.

Both players are trying to end up with more stones total than their opponent, and both play optimally the whole way through. The task is to decide whether the player who moves first can force a win no matter how well the second player defends.

The output is just a yes/no on whether the first mover can guarantee more stones than the opponent by the time every pile is gone.

EX 01

piles = [5, 3]

→ true

MINIMUM SIZE, TAKE THE BIGGER PILE

EX 02

piles = [3, 7, 2, 8]

→ true

EX 03

piles = [1, 1, 1, 1]

→ false

ALL EQUAL, THE BEST EITHER SIDE CAN DO IS TIE

the number of piles is always even
pile sizes are positive integers
only the piles at either end of the remaining row can be taken
the answer is true/false on whether the first player can force a win

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

At any point in the game, only a contiguous stretch of piles remains and only its two ends are choosable — solve the same question for every possible stretch, not just the full row.

HINT 2 THE STRUCTURE

Track the best score difference (the player to move now, minus the opponent) achievable on a stretch: taking an end wins you that pile, then the opponent plays optimally on what's left — against you.

HINT 3 ONE STEP FROM THE ANSWER

diff(i, j) = max(piles[i] − diff(i+1, j), piles[j] − diff(i, j−1)), with diff(i, i) = piles[i]. The first player forces a win exactly when diff over the whole row is greater than zero.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE EDGE-TAKER'S EDGEPATTERN · INTERVAL DP — SCORE DIFFpiles = [3, 7, 2, 8]

STEP 1

piles=[3,7,2,8]. Length-1 stretches: taking pile i alone nets a score diff of just piles[i].

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/stone-game.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = piles[:]
        for length in range(2, n + 1):
            new_dp = [0] * n
            for i in range(n - length + 1):
                j = i + length - 1
                new_dp[i] = max(piles[i] - dp[i + 1], piles[j] - dp[i])
            dp = new_dp
        return dp[0] > 0

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

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        def diff(i, j):
            if i == j:
                return piles[i]
            return max(piles[i] - diff(i + 1, j), piles[j] - diff(i, j - 1))

        return diff(0, len(piles) - 1) > 0

TIME O(2^N)SPACE O(N)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[] dp = piles.clone();
        for (int length = 2; length <= n; length++) {
            int[] newDp = new int[n];
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                newDp[i] = Math.max(piles[i] - dp[i + 1], piles[j] - dp[i]);
            }
            dp = newDp;
        }
        return dp[0] > 0;
    }
}

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

class Solution {
    private int[] piles;

    public boolean stoneGame(int[] piles) {
        this.piles = piles;
        return diff(0, piles.length - 1) > 0;
    }

    private int diff(int i, int j) {
        if (i == j) {
            return piles[i];
        }
        return Math.max(piles[i] - diff(i + 1, j), piles[j] - diff(i, j - 1));
    }
}

TIME O(2^N)SPACE O(N)JAVA · TRAINING PACE · 15 LN

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