Scale Engineer

Stone Game III

Hard
#1302Time: O(3^n), where n is the number of stones. For each state, the function branches into three recursive calls, leading to an exponential number of computations.Space: O(n), where n is the number of stones. This is due to the maximum depth of the recursion stack.
Patterns
MathDynamic ProgrammingGame Theory
Data structures
Array

Prompt

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 score of each player is the sum of the values of the stones taken. The score of each player is 0 initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob play optimally.

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

 

Example 1:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

Example 2:

Input: stoneValue = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.

Example 3:

Input: stoneValue = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

 

Constraints:

  • 1 <= stoneValue.length <= 5 * 104
  • -1000 <= stoneValue[i] <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the game's rules into a recursive solution. The problem has optimal substructure and overlapping subproblems, which are characteristics of problems solvable by recursion. We define a function that calculates the maximum score difference a player can achieve from a given starting stone. Since both players play optimally, they will always make the move that maximizes their final score relative to their opponent.

Algorithm

  • Define a recursive function solve(i) that returns the maximum score difference the current player can achieve starting from index i.
  • Base Case: If i is out of bounds (i.e., i >= n), it means there are no stones left, so the difference is 0. Return 0.
  • Recursive Step: The current player at index i has three choices:
    1. Take 1 stone: The player's score increases by stoneValue[i]. The turn passes to the opponent, who will play optimally from index i+1. The opponent's score difference from that point will be solve(i+1). Therefore, the current player's net score difference for this choice is stoneValue[i] - solve(i+1).
    2. Take 2 stones: Net score difference is (stoneValue[i] + stoneValue[i+1]) - solve(i+2).
    3. Take 3 stones: Net score difference is (stoneValue[i] + stoneValue[i+1] + stoneValue[i+2]) - solve(i+3).
  • The player will choose the option that maximizes their score difference. So, solve(i) is the maximum of the valid choices.
  • The initial call is solve(0). The final result is determined by the sign of solve(0).

Walkthrough

The core idea is to model the game as a recursive function. Let's define solve(i) as the maximum score difference the current player can get over the opponent from the stones stoneValue[i:]. When it's a player's turn at index i, they can take k stones, where k can be 1, 2, or 3. If they take k stones, their score for this turn is the sum of values of these k stones. The game then proceeds from index i+k, but now it's the opponent's turn. The opponent, playing optimally, will achieve a score difference of solve(i+k) from the remaining stones. From the current player's perspective, this is a loss of solve(i+k). Thus, the total score difference for the current player, if they take k stones, is (sum of k stones) - solve(i+k). The player will choose the k that maximizes this value. The final answer depends on solve(0): if it's positive, Alice wins; if negative, Bob wins; if zero, it's a tie.

class Solution {    public String stoneGameIII(int[] stoneValue) {        int diff = solve(stoneValue, 0);        if (diff > 0) {            return "Alice";        } else if (diff < 0) {            return "Bob";        } else {            return "Tie";        }    }     private int solve(int[] stoneValue, int i) {        int n = stoneValue.length;        if (i >= n) {            return 0;        }         int maxDiff = Integer.MIN_VALUE;        int currentSum = 0;        // Iterate through the 3 possible moves (take 1, 2, or 3 stones)        for (int k = 0; k < 3 && i + k < n; k++) {            currentSum += stoneValue[i + k];            maxDiff = Math.max(maxDiff, currentSum - solve(stoneValue, i + k + 1));        }                return maxDiff;    }}

Complexity

Time

O(3^n), where n is the number of stones. For each state, the function branches into three recursive calls, leading to an exponential number of computations.

Space

O(n), where n is the number of stones. This is due to the maximum depth of the recursion stack.

Trade-offs

Pros

  • Simple to conceptualize and implement based on the problem's recursive nature.

Cons

  • Extremely inefficient due to a large number of redundant computations for the same subproblems.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

class Solution {private  int[] stoneValue;private  Integer[] f;private  int n;public  String stoneGameIII(int[] stoneValue) {    n = stoneValue.length;    f = new Integer[n];    this.stoneValue = stoneValue;    int ans = dfs(0);    if (ans == 0) {      return "Tie";    }    return ans > 0 ? "Alice" : "Bob";  }private  int dfs(int i) {    if (i >= n) {      return 0;    }    if (f[i] != null) {      return f[i];    }    int ans = -(1 << 30);    int s = 0;    for (int j = 0; j < 3 && i + j < n; ++j) {      s += stoneValue[i + j];      ans = Math.max(ans, s - dfs(i + j + 1));    }    return f[i] = ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem