We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stone Game III

Number: 1522

Difficulty: Hard

Paid? No

Companies: Google, Bloomberg

Problem Description

Alice and Bob play a turn-based game with a row of stones where each stone has an integer value. On each turn, a player can take 1, 2, or 3 stones from the start of the row. The players aim to maximize their total score, and both play optimally. The task is to determine the winner: return "Alice" if she wins, "Bob" if he wins, or "Tie" if the scores at the end are equal.

Key Insights

  • Use dynamic programming to compute the maximum score difference a player can achieve starting from any index.
  • Define dp[i] as the maximum net score (current player's score minus opponent's score) achievable from index i.
  • The recurrence relation is: dp[i] = max(sum(stones[i...j]) - dp[j+1]) for j from i to i+2 (as players can pick 1 to 3 stones).
  • Use backward induction (starting from the end) and base case dp[n] = 0, where n is the length of the stone array.
  • The final decision is based on dp[0]: if positive, Alice wins; if negative, Bob wins; and if zero, it's a Tie.

Space and Time Complexity

Time Complexity: O(n) where n is the number of stones, since each state is computed with a constant number of iterations (up to 3). Space Complexity: O(n) for the dp array used to store computed states.

Solution

We solve this problem using bottom-up dynamic programming. The main idea is to keep a dp array where each dp[i] represents the maximum score difference (current player's score minus opponent's score) that can be achieved starting from the i-th stone. At each position i, we consider taking 1, 2, or 3 stones (ensuring we stay within the bounds) and then subtract the dp-value corresponding to the opponent's best response. By iterating backward from the last stone, we can fill out dp[0] to determine the outcome when both players play optimally.

Code Solutions

# Python implementation of the Stone Game III solution
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        # Initialize dp array with a very small number to handle negative values
        dp = [-10**9] * (n + 1)
        dp[n] = 0  # Base case: no stones left yields a score difference of 0
        
        # Iterate backwards from the last stone to the first
        for i in range(n - 1, -1, -1):
            current_sum = 0
            # Try taking 1, 2, or 3 stones
            for j in range(i, min(i + 3, n)):
                current_sum += stoneValue[j]
                dp[i] = max(dp[i], current_sum - dp[j + 1])
        
        # Determine the winner based on dp[0]
        if dp[0] > 0:
            return "Alice"
        elif dp[0] < 0:
            return "Bob"
        else:
            return "Tie"
← Back to All Questions