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

Number: 909

Difficulty: Medium

Paid? No

Companies: Google, Cisco, Bloomberg, Microsoft, Amazon, TikTok

Problem Description

Alice and Bob play a game with an even number of piles of stones arranged in a row. Each pile contains a positive integer number of stones and the total number of stones is odd, ensuring there will be no tie. Players take turns choosing to take the entire pile from either the beginning or the end of the row. Alice starts first. Assuming both play optimally, determine if Alice wins the game.

Key Insights

  • Because the total number of piles is even, Alice can always choose either odd-indexed or even-indexed piles to force a win if she plays optimally.
  • A dynamic programming approach can be used where the state dp[i][j] represents the maximum net score (difference between the current player’s score and the opponent’s score) obtainable from piles i to j.
  • The recurrence relation is dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]), as the current player chooses the option that maximizes their score difference.
  • Alternatively, by using game theory and the parity property of indices, it can be mathematically shown that Alice has a winning strategy.

Space and Time Complexity

Time Complexity: O(n^2), where n is the number of piles
Space Complexity: O(n^2) for the DP table (this can be optimized to O(n) with careful observation)

Solution

The solution utilizes a dynamic programming approach. We define a 2D array dp where dp[i][j] represents the maximum difference the current player can achieve over the opponent from the subarray piles[i...j]. The base case is when i equals j, and then dp[i][i] equals piles[i] because there is only one pile to choose from.

For a general subarray from index i to j, the current player has two choices:

  1. Pick the leftmost pile (piles[i]). The net effect is piles[i] minus the optimal result of the opponent from the subarray (i+1, j) which is represented by dp[i+1][j].
  2. Pick the rightmost pile (piles[j]). The net effect is piles[j] minus the optimal result from the subarray (i, j-1), given by dp[i][j-1].

Thus, dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]). The final decision is given by dp[0][n-1]. If the value is greater than 0, Alice wins; otherwise, Bob wins.

Code Solutions

# Python implementation with detailed comments

def stoneGame(piles):
    n = len(piles)
    # Create a DP table initialized with zeroes.
    dp = [[0] * n for _ in range(n)]
    
    # Base case: when the subarray length is 1, the only option is to take that pile.
    for i in range(n):
        dp[i][i] = piles[i]
    
    # Build the DP table in a bottom-up manner from subarrays of length 2 to n.
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1  # define the endpoint of the subarray
            # Choose the optimal move between picking the leftmost or the rightmost pile.
            dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
    
    # If Alice's net difference is positive, she wins.
    return dp[0][n - 1] > 0

# Example usage:
print(stoneGame([5,3,4,5]))  # Output: True
← Back to All Questions