Stone Game III

Problem Description

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

Alice and Bob take turns, with Alice starting first. On each player’s turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.

The game ends when no more stones are left. The winner is the one with the higher score. If they have the same score, it’s a draw.

Return "Alice" if Alice will win, "Bob" if Bob will win, or "Tie" if they end the game with the same score.

Assume both players play optimally.

Examples

Constraints

• 1 ≤ stoneValue.length ≤ 5 * 10⁴
• -1000 ≤ stoneValue[i] ≤ 1000

Game Theory: Maximize Score Difference

Since the game is zero-sum, a player’s goal is to maximize their own score minus their opponent’s score.

Let dp[i] be the maximum relative score difference the current player can achieve starting from index i of the array. From index i, the player can take 1, 2, or 3 stones:

• Take 1 stone: score is stoneValue[i] - dp[i + 1] (the player gets stoneValue[i], and the opponent gets at most dp[i+1] relative advantage from the remaining stones).
• Take 2 stones: score is stoneValue[i] + stoneValue[i + 1] - dp[i + 2].
• Take 3 stones: score is stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3].

Thus, dp[i] is the maximum of these three options.

We compute dp[i] from right to left starting from n - 1 down to 0. If dp[0] > 0, Alice wins. If dp[0] < 0, Bob wins. If dp[0] == 0, it’s a Tie.

Solution: 1D DP

class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 4]; // add padding to avoid index checks

        for (int i = n - 1; i >= 0; i--) {
            int take1 = stoneValue[i] - dp[i + 1];
            int take2 = Integer.MIN_VALUE;
            int take3 = Integer.MIN_VALUE;

            if (i + 1 < n) {
                take2 = stoneValue[i] + stoneValue[i + 1] - dp[i + 2];
            }
            if (i + 2 < n) {
                take3 = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3];
            }

            dp[i] = Math.max(take1, Math.max(take2, take3));
        }

        if (dp[0] > 0) return "Alice";
        if (dp[0] < 0) return "Bob";
        return "Tie";
    }
}

class Solution:
    def stoneGameIII(self, stoneValue: list[int]) -> str:
        n = len(stoneValue)
        dp = [0] * (n + 3)  # add padding to avoid index checks

        for i in range(n - 1, -1, -1):
            # option 1: take 1 stone
            take1 = stoneValue[i] - dp[i + 1]
            
            # option 2: take 2 stones
            take2 = float('-inf')
            if i + 1 < n:
                take2 = stoneValue[i] + stoneValue[i + 1] - dp[i + 2]
                
            # option 3: take 3 stones
            take3 = float('-inf')
            if i + 2 < n:
                take3 = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]

            dp[i] = max(take1, take2, take3)

        if dp[0] > 0:
            return "Alice"
        if dp[0] < 0:
            return "Bob"
        return "Tie"

#include <vector>
#include <string>
#include <algorithm>
#include <climits>

class Solution {
public:
    std::string stoneGameIII(std::vector<int>& stoneValue) {
        int n = stoneValue.size();
        std::vector<int> dp(n + 3, 0);

        for (int i = n - 1; i >= 0; i--) {
            int take1 = stoneValue[i] - dp[i + 1];
            int take2 = INT_MIN;
            int take3 = INT_MIN;

            if (i + 1 < n) {
                take2 = stoneValue[i] + stoneValue[i + 1] - dp[i + 2];
            }
            if (i + 2 < n) {
                take3 = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3];
            }

            dp[i] = std::max({take1, take2, take3});
        }

        if (dp[0] > 0) return "Alice";
        if (dp[0] < 0) return "Bob";
        return "Tie";
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of stoneValue. We iterate backwards once.
• Space Complexity: O(N) to store the DP values. (Can be optimized to O(1) space since we only need the last 3 values of dp).

← All Problems