1406. Stone Game III
Problem Description
Alice and Bob are playing a game with an arrangement of stones in a row. Each stone has a value, and these values are listed in an array called stoneValue
. The players take turns, with Alice going first, and on each player's turn, they may take 1, 2, or 3 stones from the beginning of the remaining row of stones.
The score for a player increases by the value of the stones they take, and everyone starts with a score of 0. The goal is to finish the game with the highest score, and it is possible that the game ends in a tie if both players have the same score when all the stones have been taken.
The key part of the problem is that both players will play optimally, meaning they will make the best possible moves to maximize their own score.
The objective is to determine the winner of the game or to find out if it will end in a tie, based on the values of the stones.
Intuition
To solve this problem, we need to use dynamic programming, as we're looking for the best strategy over several turns, considering the impact of each possible move.
The intuition behind the solution is to look at each position in the array and decide the best move for the player whose turn it is. Since each player is trying to maximize their own score, they should be looking to maximize their current score minus whatever score the opponent would get after that move. This is because while a player aims to increase their score, they should also try to minimize the future opportunities for the opponent.
The dynamic programming function, here defined as dfs(i)
, returns the maximum score difference (player score - opponent score) from the i
th stone to the end of the array. When it's the current player's turn, they look ahead at up to 3 moves and calculate the score difference they would get if the next player played optimally from that point. We recursively calculate dfs(i)
for the possible moves and choose the one with the maximum score difference.
Since Python's @cache
decorator is being used, computations for each position are remembered and not recalculated multiple times, which greatly improves the efficiency.
After performing the DFS, the final answer is compared against 0. If the final score difference resulting from dfs(0)
(starting at the first stone) is zero, it is a 'Tie.' If greater than zero, the current player (Alice, since she starts) wins, and if it is less than zero, it means the second player (Bob) wins.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The solution is implemented using dynamic programming, one of the most powerful algorithms in solving optimization problems, especially those involving the best strategy to play a game. In this case, memoization via Python's @cache
decorator is used to store the results of subproblems.
The dfs(i)
function defined within the stoneGameIII
method is the core of the solution, which represents the best score difference that can be obtained starting with the i
th stone.
Here's a breakdown of how the dfs(i)
function operates:
- It takes a parameter
i
which represents the index of the starting stone in thestoneValue
list. - The function is initially called with
i = 0
as we start evaluating from the first stone. - A check is made to see if
i
is beyond the last stone in the array, in which case the function returns0
, indicating no more scores can be obtained. - The function maintains two variables:
ans
, which will store the maximum score difference possible from this position, ands
, which is the cumulative sum of stone values that have been picked. - A loop explores taking 1, 2, or 3 stones from the current position by incrementing
j
. The constraint is to break out of the loop if the end of the stones array is reached. - For each possible move (taking
j
stones), we calculate the sums
of values of stones taken, and we calculate a potential answer ass - dfs(i + j + 1)
. This calculation ensures we consider the opponent's optimal play after our move. - We update
ans
to be the maximum of itself or the newly calculated potential answer. - Once we loop through all possible moves, we return the maximum answer.
The memoization ensures that we don't compute the same state multiple times, reducing the problem to linear complexity.
Finally, when the dfs(0)
is called, we check if the result is 0
, indicating a tie. If it's positive, Alice wins because it means she can have a greater score difference by playing optimally. If it's negative, Bob wins for the opposite reason.
The data structure used here is essentially the list called stoneValue
. The @cache
decorator creates an implicit hashtable-like structure to remember previously calculated results of the dfs
function.
This approach uses the concept of minimax, which is widely used in decision-making and turn-based games, to always make the best move considering the opponent will also play optimally.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example. Suppose we have the stoneValue
array as follows: [1,2,3,7]
.
Alice and Bob will play optimally, taking turns starting with Alice. Let's see how the dfs
function would be used to determine the game's outcome.
- Initially,
dfs(0)
is called since Alice starts with the first stone. - At
i = 0
, there are three choices for Alice:- Take
stoneValue[0]
which is1
, and thendfs(1)
will be called for Bob. - Take
stoneValue[0]
andstoneValue[1]
which sums to3
, and thendfs(2)
will be called for Bob. - Take
stoneValue[0]
,stoneValue[1]
, andstoneValue[2]
which sums to6
, and thendfs(3)
will be called for Bob.
- Take
dfs(1)
will be Bob's turn with remaining stones[2,3,7]
. Bob has the same choice to take 1, 2, or 3 stones, and after each choice, a newdfs
with the appropriate index would be called for Alice.- This process continues until
i
reaches the length of thestoneValue
array, at which point the function returns0
since no stones are left to take. - During each call,
dfs
calculates the maximum score difference Alice or Bob can have at that point. For instance, if Alice takes one stone, then Bob can optimally choose the best outcome from the remaining stones, and the score difference is updated accordingly. - Eventually, all possible options and their score differences are computed, and
dfs(i)
will return the optimal score difference the current player can achieve fromi
to the end of the array.
The game would unfold as follows, showing the choices and corresponding dfs
calls:
dfs(0)
:- Choice 1: Take
1
.dfs(1)
(Bob's turn) is now evaluated. - Choice 2: Take
1 + 2 = 3
.dfs(2)
(Bob's turn) is now evaluated. - Choice 3: Take
1 + 2 + 3 = 6
.dfs(3)
(Bob's turn) is now evaluated.
- Choice 1: Take
dfs(1)
(Bob's turn with[2,3,7]
):- Bob will look ahead and follow similar steps, aiming to minimize Alice's score following his moves.
After evaluating all the possibilities, dfs(0)
will yield the best score difference Alice can achieve by taking stones optimally from the beginning of the array. If the score difference is:
- Greater than 0: Alice wins.
- Less than 0: Bob wins.
- Exactly 0: The game results in a tie.
For this example, Alice can secure a win by taking the first stone (with a value of 1), because now the score difference (dfs(0)
) can be maximized as follows:
- Alice takes
1
, anddfs(1)
is called. - If Bob takes
2
, Alice can take3
and7
and wins. If Bob takes2
and3
, Alice takes7
and still wins. Hence Bob will choose the option that minimizes loss, which might be taking2
, making the sequence of plays[1], [2], [3,7]
, and Alice wins by 7 (Alice's total: 11 - Bob's total: 4 = 7).
Using this strategy, we understand that dfs(0)
would return a positive score indicating Alice as the winner. Each call to dfs
was efficiently processed due to memoization, which saved the state to prevent re-evaluation.
Solution Implementation
1from functools import lru_cache # Import the lru_cache decorator from functools
2from math import inf # Import 'inf' from the math library to represent infinity
3
4class Solution:
5 def stoneGameIII(self, stone_values: List[int]) -> str:
6 """
7 Determine the result of the stone game III.
8
9 :param stone_values: List[int] - A list of integers representing the values of stones.
10 :return: str - The result of the game, either 'Alice', 'Bob', or 'Tie'.
11 """
12 # Define the depth-first search function with memoization
13 @lru_cache(maxsize=None)
14 def dfs(current_index: int) -> int:
15 """
16 Calculate the maximum score difference the player can obtain starting from 'current_index'.
17
18 :param current_index: int - The current index a player is at.
19 :return: int - The maximum score difference.
20 """
21 if current_index >= total_stones:
22 return 0
23
24 # Initialize the answer to negative infinity and a sum accumulator
25 max_score_diff, accumulated_sum = -inf, 0
26
27 # The player can pick 1, 2, or 3 stones in a move
28 for j in range(3):
29 # If the range exceeds the length of stone_values, stop the loop
30 if current_index + j >= total_stones:
31 break
32 # Accumulate the value of stones picked
33 accumulated_sum += stone_values[current_index + j]
34 # Calculate the max score difference recursively by subtracting the opponent's best score after the current player's turn
35 max_score_diff = max(max_score_diff, accumulated_sum - dfs(current_index + j + 1))
36
37 return max_score_diff
38
39 # Get the total number of stones
40 total_stones = len(stone_values)
41 # Start the game from index 0 to get the overall answer
42 final_score_diff = dfs(0)
43
44 # Compare the final score difference to determine the winner
45 if final_score_diff == 0:
46 return 'Tie'
47 elif final_score_diff > 0:
48 return 'Alice'
49 else:
50 return 'Bob'
51
1class Solution {
2 private int[] stoneValues; // An array to hold the values of the stones.
3 private Integer[] memoization; // A memoization array to store results of subproblems.
4 private int totalStones; // The total number of stones.
5
6 // Determines the outcome of the stone game III.
7 public String stoneGameIII(int[] stoneValues) {
8 totalStones = stoneValues.length; // Initialize the total number of stones.
9 this.stoneValues = stoneValues; // Set the class's stoneValues array.
10 memoization = new Integer[totalStones]; // Initialize the memoization array.
11
12 // Result of the DFS to compare against.
13 int result = dfs(0);
14
15 if (result == 0) {
16 return "Tie"; // If result is zero, then the game is tied.
17 }
18
19 // If the result is positive, Alice wins; otherwise, Bob wins.
20 return result > 0 ? "Alice" : "Bob";
21 }
22
23 // Depth-First Search with memoization to calculate the optimal result.
24 private int dfs(int index) {
25 // Base case: if the index is out of the right boundary of array.
26 if (index >= totalStones) {
27 return 0;
28 }
29
30 // Return the already computed result if present, avoiding redundant computation.
31 if (memoization[index] != null) {
32 return memoization[index];
33 }
34
35 int maxDifference = Integer.MIN_VALUE; // Initialize to the smallest possible value.
36 int sum = 0; // Sum to store the total values picked up until now.
37
38 // Try taking 1 to 3 stones starting from the current index 'i' and calculate
39 // the maximum score difference taking the subproblem (i+j+1) into account.
40 for (int j = 0; j < 3 && index + j < totalStones; ++j) {
41 sum += stoneValues[index + j]; // Increment sum with stone value.
42 // Update maxDifference with the maximum of its current value and the score
43 // difference. The score difference is current sum - result of dfs(i + j + 1).
44 maxDifference = Math.max(maxDifference, sum - dfs(index + j + 1));
45 }
46
47 // Store the result in memoization and return it.
48 return memoization[index] = maxDifference;
49 }
50}
51
1#include <vector>
2#include <cstring>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9 // Function to decide the winner of the stone game III
10 string stoneGameIII(vector<int>& stoneValue) {
11 int n = stoneValue.size(); // Get the number of stones
12 vector<int> dp(n, INT_MIN); // Initialize the dynamic programming table with minimum int values
13
14 // Recursive lambda function to perform depth-first search
15 function<int(int)> dfs = [&](int index) -> int {
16 if (index >= n) {
17 return 0; // Base case: if we've reached or exceeded the number of stones, the score is 0
18 }
19 if (dp[index] != INT_MIN) {
20 return dp[index]; // If the value is already computed, return it
21 }
22 int maxScore = INT_MIN; // Initialize the max score for the current player
23 int sum = 0; // Variable to store the cumulative value of stones picked up
24
25 // Explore upto 3 moves ahead, because a player can pick 1, 2, or 3 stones
26 for (int j = 0; j < 3 && index + j < n; ++j) {
27 sum += stoneValue[index + j]; // Accumulate value of stones picked
28 maxScore = max(maxScore, sum - dfs(index + j + 1)); // Choose the move which gives the max score
29 }
30 dp[index] = maxScore; // Memoize the result for the current index
31 return maxScore;
32 };
33
34 int finalScore = dfs(0); // Start the game from the first stone
35
36 // Using the calculated final score, determine the winner or if it's a tie
37 if (finalScore == 0) {
38 return "Tie";
39 }
40 return finalScore > 0 ? "Alice" : "Bob";
41 }
42};
43
1// Function that determines the winner of the stone game
2function stoneGameIII(stoneValues: number[]): string {
3 const stoneCount = stoneValues.length;
4 const INFINITY = 1 << 30; // A representation of infinity.
5 const dp: number[] = new Array(stoneCount).fill(INFINITY); // DP array initialized with 'infinity' for memoization.
6
7 // Helper function that uses Depth First Search and dynamic programming to calculate the score
8 const dfs = (currentIndex: number): number => {
9 if (currentIndex >= stoneCount) { // Base case: no stones left.
10 return 0;
11 }
12 if (dp[currentIndex] !== INFINITY) { // If value already computed, return it from memoization storage.
13 return dp[currentIndex];
14 }
15
16 let maxDiff = -INFINITY; // Initialize max difference as negative infinity.
17 let currentSum = 0; // Holds the running total sum of stone values.
18 for (let count = 0; count < 3 && currentIndex + count < stoneCount; ++count) {
19 currentSum += stoneValues[currentIndex + count];
20 // Recursive call to dfs for the opponent's turn.
21 // Update maxDiff to be the maximum value Alice can get by considering the current pick.
22 maxDiff = Math.max(maxDiff, currentSum - dfs(currentIndex + count + 1));
23 }
24 // Store the computed maxDiff value in the dp array (memoization)
25 dp[currentIndex] = maxDiff;
26 return maxDiff;
27 };
28
29 const finalScore = dfs(0); // Start the game with the first stone.
30
31 if (finalScore === 0) {
32 return 'Tie'; // If final score is 0, then the game is a tie.
33 }
34 // If final score is positive, Alice wins; otherwise, Bob wins.
35 return finalScore > 0 ? 'Alice' : 'Bob';
36}
37
Time and Space Complexity
Time Complexity
The time complexity of the function stoneGameIII
is determined by the recursion process performed by the helper function dfs
. In this function, the algorithm attempts to maximize the score for the current player by choosing up to three consecutive stones (which is implemented in the for loop that iterates at most three times).
The memoization (through the @cache
decorator) stores the results of the subproblems, which are the optimal scores starting from each index i
. There are n
possible indices to start from (where n
is the length of stoneValue
), and since each function call of dfs
examines at most 3 different scenarios before recursion, the total number of operations needed is proportional to n
.
Hence, the time complexity is O(n)
because each state is computed only once due to memoization, and the recursive calls made from each state are at most three.
Space Complexity
The space complexity of stoneGameIII
is determined by two factors: the space used for recursion (the recursion depth) and the space used to store the results of subproblems (due to memoization).
-
Recursion Depth: Since the function
dfs
is called recursively and can potentially make up to three recursive calls for each call made, the depth of the recursion tree could theoretically go up ton
in a worst-case scenario. However, due to memoization, many recursive calls are pruned, and thus, the true recursion depth is limited. Generally, the recursion does not go beyondn
. -
Memoization Storage: The memoization of
dfs
subproblem results is implemented through the@cache
decorator, which could potentially store results for each of then
starting indices.
Combining these two factors, the space complexity is also O(n)
, primarily due to the space needed to store the computed values for memoization for each possible starting index and the call stack for the recursive calls.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!