How do you solve Stone Game II on LeetCode?

Stone Game II (LeetCode #1140) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Understanding game theory helps in optimizing choices.

What is the brute force solution for Stone Game II?

The brute force approach for Stone Game II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves simulating every possible move Alice can make and calculating the resulting stones she can collect. This method is straightforward but inefficient, as it explores all combinations of moves. The optimal Optimal Solution approach improves this to O(n²).

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

Stone Game II uses the following concepts: Array, Math, Dynamic Programming, Prefix Sum, Game Theory. The recommended patterns to study are: Dynamic Programming, Game Theory.

What are the interview tips for Stone Game II?

Explain your thought process clearly while coding. Consider edge cases and constraints before finalizing your approach. Practice similar problems to build confidence in dynamic programming.

What are common mistakes when solving Stone Game II?

Not considering both players play optimally. Failing to use prefix sums for efficient calculations.

#1140

Stone Game II

Medium

ArrayMathDynamic ProgrammingPrefix SumGame TheoryDynamic ProgrammingGame Theory

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

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

💡

Intuition

Time O(n²)Space O(n)

Using dynamic programming, we can store the results of subproblems to avoid redundant calculations. This approach significantly reduces the number of computations by leveraging previously computed results.

⚙️

Algorithm

3 steps

1Step 1: Create a DP table where dp[i][m] represents the maximum stones Alice can collect starting from pile i with current M value m.
2Step 2: Iterate backwards through the piles, filling in the DP table based on optimal choices Alice can make.
3Step 3: Use the prefix sum to quickly calculate the total stones available for any range of piles.

solution.py15 lines

1# Full working Python code
2class Solution:
3    def stoneGameII(self, piles):
4        n = len(piles)
5        dp = [[0] * (n + 1) for _ in range(n)]
6        prefix = [0] * (n + 1)
7        for i in range(n - 1, -1, -1):
8            prefix[i] = prefix[i + 1] + piles[i]
9            for m in range(1, n + 1):
10                max_stones = 0
11                for x in range(1, 2 * m + 1):
12                    if i + x <= n:
13                        max_stones = max(max_stones, prefix[i] - dp[i + x][max(m, x)])
14                dp[i][m] = max_stones
15        return dp[0][1]

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops, but we now use O(n) space for the DP table, which allows us to store results and avoid redundant calculations.

1Understanding game theory helps in optimizing choices.
2Dynamic programming is effective for problems with overlapping subproblems.

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