Stone Game III

Stone Game III

What is this problem about?

In Stone Game III, Alice and Bob take turns taking 1, 2, or 3 piles from the beginning of the row. The total score is the sum of the stones in the piles taken. The game ends when no more piles are left. The player with the highest score wins. You need to return "Alice", "Bob", or "Tie".

Why is this asked in interviews?

This "Hard" problem tests your ability to implement the Minimax strategy using Dynamic Programming. It's more straightforward than Stone Game II because the number of choices is fixed (1, 2, or 3), but it still requires careful handling of relative scores. It assesses your ability to think about "optimal play" in a competitive setting.

Algorithmic pattern used

The pattern is Dynamic Programming (Linear). We define dp[i] as the maximum relative score (Alice's score - Bob's score) the current player can achieve starting from index $i$. From index $i$, the player can:

• Take 1 pile: relative_score = piles[i] - dp[i+1]
• Take 2 piles: relative_score = piles[i] + piles[i+1] - dp[i+2]
• Take 3 piles: relative_score = piles[i] + piles[i+1] + piles[i+2] - dp[i+3] The player will choose the maximum of these three options.

Example explanation (use your own example)

Piles: [1, 2, 3, 7].

• From the end (index 3): Only 1 pile left (7). dp[3] = 7.
• From index 2: Can take [3] (rel: 3-7=-4) or [3, 7] (rel: 10). dp[2] = 10.
• From index 1: Can take [2] (rel: 2-10=-8), [2, 3] (rel: 5-7=-2), or [2, 3, 7] (rel: 12). dp[1] = 12.
• From index 0: Alice tries taking 1, 2, or 3 piles and subtracts Bob's best possible score from the remaining piles. If the final dp[0] > 0, Alice wins.

Common mistakes candidates make

• Absolute vs Relative Score: Trying to track both Alice's and Bob's scores separately in the DP, which is more complex than tracking the difference.
• Base cases: Not handling the end of the array correctly (out of bounds).
• Tie condition: Forgetting to return "Tie" if the final relative score is exactly 0.
• Initialization: Not initializing the DP array with a sufficiently small value (negative infinity) since relative scores can be negative.

Interview preparation tip

For zero-sum games, tracking the difference between scores (myScore - yourScore) is usually much simpler than tracking two separate scores. This is a key insight for Game Theory, Dynamic Programming interview pattern questions.