How do you solve Stone Game VI on LeetCode?

Stone Game VI (LeetCode #1686) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Both players will always choose the stone that maximizes their combined score.

What is the brute force solution for Stone Game VI?

The brute force approach for Stone Game VI is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we explore all possible sequences of moves by Alice and Bob. This means simulating every possible way the game could unfold, which is simple but inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Stone Game VI?

Stone Game VI uses the following concepts: Array, Math, Greedy, Sorting, Heap (Priority Queue), Game Theory. The recommended patterns to study are: Greedy Algorithms, Sorting.

What are the interview tips for Stone Game VI?

Always clarify the rules of the game and how players score. Think about how to represent the problem in a way that highlights optimal choices. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Stone Game VI?

Failing to account for the fact that both players play optimally. Not considering the combined value of stones when making selections.

#1686

Stone Game VI

Medium

ArrayMathGreedySortingHeap (Priority Queue)Game TheoryGreedy AlgorithmsSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

In the optimal solution, we recognize that both players will always choose the stone that maximizes their combined score. Thus, we can sort the stones based on the total value they provide to both players and let them take turns picking the highest valued stones.

⚙️

Algorithm

3 steps

1Step 1: Create a list of tuples containing the index and the sum of values for each stone from both players.
2Step 2: Sort this list in descending order based on the sum of values.
3Step 3: Alternate picking stones based on the sorted order, calculating scores for Alice and Bob.

solution.py10 lines

1def stoneGameVI(aliceValues, bobValues):
2    n = len(aliceValues)
3    stones = sorted(range(n), key=lambda i: -(aliceValues[i] + bobValues[i]))
4    alice_score, bob_score = 0, 0
5    for i in range(n):
6        if i % 2 == 0:
7            alice_score += aliceValues[stones[i]]
8        else:
9            bob_score += bobValues[stones[i]]
10    return (alice_score > bob_score) - (alice_score < bob_score)

ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step, while the space complexity is O(n) for storing the indices of the stones.

1Both players will always choose the stone that maximizes their combined score.
2Sorting based on the total value of stones allows us to simulate optimal play efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.