Stone Game

NeetCode: Stone Game · LeetCode: 877. Stone Game · Difficulty: Medium

Alice and Bob play with an even number of piles of stones in a row, piles[i] stones in pile i. The total number of stones is odd, so there are no ties. They alternate turns, Alice first; on each turn a player takes the whole pile from either the beginning or the end of the row. The player with more stones at the end wins. Both play optimally. Return true if Alice wins.

Example

Text

Input:  piles = [5, 3, 4, 5]    Output: true   (Alice takes 5, ends with 9 against 7)
Input:  piles = [3, 7, 2, 3]    Output: true

Brute force: minimax recursion

Instead of tracking two scores, track the difference "current player's stones minus opponent's stones" for the remaining piles [l, r]. The player to move takes either end and then faces the opponent's best difference on what is left:

f(l, r) = max(piles[l] - f(l+1, r), piles[r] - f(l, r-1))

with f(l, l) = piles[l]. Alice wins when f(0, n-1) > 0. Every call branches in two, so the time is O(2^n).

Java

class Solution {
    public boolean stoneGame(int[] piles) {
        if (piles.length == 0) return false;
        return f(piles, 0, piles.length - 1) > 0;
    }

    private int f(int[] p, int l, int r) {
        if (l == r) return p[l];
        return Math.max(p[l] - f(p, l + 1, r), p[r] - f(p, l, r - 1));
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.stoneGame(new int[]{5, 3, 4, 5}));
        System.out.println(s.stoneGame(new int[]{3, 7, 2, 3}));
        System.out.println(s.stoneGame(new int[]{}));
    }
}

Output

true
true
false

Time: O(2^n). Space: O(n) recursion depth.

Better: memoization

Only the O(n^2) intervals [l, r] can appear, so cache f(l, r). The cache is an Integer[][]: Integer is the object form of int, so an unfilled entry is null. A difference can be zero or negative, so a sentinel number such as 0 or -1 would be ambiguous.

Java

class Solution {
    public boolean stoneGame(int[] piles) {
        if (piles.length == 0) return false;
        int n = piles.length;
        Integer[][] memo = new Integer[n][n];
        return f(piles, 0, n - 1, memo) > 0;
    }

    private int f(int[] p, int l, int r, Integer[][] memo) {
        if (l == r) return p[l];
        if (memo[l][r] != null) return memo[l][r];
        int res = Math.max(p[l] - f(p, l + 1, r, memo), p[r] - f(p, l, r - 1, memo));
        memo[l][r] = res;
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.stoneGame(new int[]{5, 3, 4, 5}));
        System.out.println(s.stoneGame(new int[]{3, 7, 2, 3}));
        System.out.println(s.stoneGame(new int[]{}));
    }
}

Output

true
true
false

Time: O(n^2). Space: O(n^2).

Optimal: interval DP with one row

Fill by growing intervals: dp[i][j] needs dp[i+1][j] (row below) and dp[i][j-1] (left neighbour), so with i running from the end down to 0, a single array works. Inside the loop dp[j] still holds dp[i+1][j], and dp[j-1] already holds dp[i][j-1].

Java

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.stoneGame(new int[]{5, 3, 4, 5}));
        System.out.println(s.stoneGame(new int[]{3, 7, 2, 3}));
        System.out.println(s.stoneGame(new int[]{}));
    }
}

Output

true
true
false

Time: O(n^2). Space: O(n).

For this exact problem (an even number of piles and an odd total) the answer is always true, so public boolean stoneGame(int[] piles) { return true; } passes in O(1). The reason: the piles at even indices and the piles at odd indices are disjoint sets that partition the row, and their sums differ because the total is odd. Alice can commit to taking all the even-indexed piles or all the odd-indexed ones. Taking pile 0 leaves Bob only odd-indexed ends, and taking pile n-1 leaves him only even-indexed ends, so she can force whichever set has the larger sum. The DP above also handles variants where that argument does not apply, such as an odd number of piles.