Stone Game III

NeetCode: Stone Game III · LeetCode: 1406. Stone Game III · Difficulty: Hard

Alice and Bob play with a row of piles stoneValue (an int[]). Alice moves first. On a turn a player takes 1, 2 or 3 piles from the front of the remaining row and adds their values (possibly negative) to their score. The game ends when no piles remain; the higher score wins. Both play optimally. Return "Alice", "Bob" or "Tie".

Example

Text

Input:  stoneValue = [1, 2, 3, 7]     Output: "Bob"
Input:  stoneValue = [1, 2, 3, -9]    Output: "Alice"
Input:  stoneValue = [1, 2, 3, 6]     Output: "Tie"

Brute force: plain recursion on the score difference

Each player only needs to maximise the difference of scores, so define diff(i) = (current player's score minus the opponent's) from the position where piles i.. remain. Taking k piles gives sum(i..i+k) and then the opponent faces diff(i + k), which is subtracted:

diff(i) = max over k in 1 to 3 of (sum of the k piles) - diff(i + k), and diff(n) = 0.

The sign of diff(0) decides the game. Each call branches three ways, so this is O(3^n). The solutions use LeetCode's signature String stoneGameIII(int[] stoneValue); the scores are int sums, which wrap silently on overflow, so very large inputs would need long.

Java

class Solution {
    private int diff(int[] stoneValue, int i) {
        if (i >= stoneValue.length) {
            return 0;
        }
        int best = Integer.MIN_VALUE;
        int taken = 0;
        for (int k = 1; k <= 3; k++) {
            if (i + k > stoneValue.length) {
                break;
            }
            taken += stoneValue[i + k - 1];
            best = Math.max(best, taken - diff(stoneValue, i + k));
        }
        return best;
    }

    public String stoneGameIII(int[] stoneValue) {
        int d = diff(stoneValue, 0);
        return d > 0 ? "Alice" : d < 0 ? "Bob" : "Tie";
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, 7}));
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, -9}));
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, 6}));
        System.out.println(sol.stoneGameIII(new int[] {-1, -2, -3}));
    }
}

Output

Bob
Alice
Tie
Tie

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

Better: DP table

diff(i) depends only on i, so there are n + 1 distinct states, each computed from three choices. Filling a table from the back (dp[n] = 0, then dp[n-1], dp[n-2], ...) removes the recursion.

Java

class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 1]; // dp[i] = best score difference from pile i
        for (int i = n - 1; i >= 0; i--) {
            int best = Integer.MIN_VALUE;
            int taken = 0;
            for (int k = 1; k <= 3; k++) {
                if (i + k > n) {
                    break;
                }
                taken += stoneValue[i + k - 1];
                best = Math.max(best, taken - dp[i + k]);
            }
            dp[i] = best;
        }
        int d = dp[0];
        return d > 0 ? "Alice" : d < 0 ? "Bob" : "Tie";
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, 7}));
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, -9}));
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, 6}));
        System.out.println(sol.stoneGameIII(new int[] {-1, -2, -3}));
        System.out.println(sol.stoneGameIII(new int[] {}));
    }
}

Output

Bob
Alice
Tie
Tie
Tie

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

Optimal: keep only the last three states

dp[i] reads only dp[i+1], dp[i+2] and dp[i+3], so three variables replace the array.

Walkthrough for [1, 2, 3, 7] (differences, computed right to left): dp[4] = 0, dp[3] = 7, dp[2] = max(3 - 7, 3 + 7 - 0) = 10, dp[1] = max(2 - 10, 2 + 3 - 7, 2 + 3 + 7 - 0) = 12, dp[0] = max(1 - 12, 1 + 2 - 10, 1 + 2 + 3 - 7) = -1. Negative, so Bob wins.

Java

class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        // a, b, c = dp[i+1], dp[i+2], dp[i+3]; positions past the end are 0.
        int a = 0, b = 0, c = 0;
        for (int i = n - 1; i >= 0; i--) {
            int best = stoneValue[i] - a;
            if (i + 1 < n) {
                best = Math.max(best, stoneValue[i] + stoneValue[i + 1] - b);
            }
            if (i + 2 < n) {
                best = Math.max(best, stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - c);
            }
            c = b;
            b = a;
            a = best;
        }
        return a > 0 ? "Alice" : a < 0 ? "Bob" : "Tie";
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, 7}));
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, -9}));
        System.out.println(sol.stoneGameIII(new int[] {1, 2, 3, 6}));
        System.out.println(sol.stoneGameIII(new int[] {-1, -2, -3}));
        System.out.println(sol.stoneGameIII(new int[] {}));
    }
}

Output

Bob
Alice
Tie
Tie
Tie

Time: O(n). Space: O(1).

Modelling the score difference instead of each player's score needs only one value per state: the game reduces to maximising the current player's lead, so no state for whose turn it is is required.