How do you solve Stone Game on LeetCode?

Stone Game (LeetCode #877) 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: Alice can always win if both play optimally due to the even number of piles.

What is the brute force solution for Stone Game?

The brute force approach for Stone Game is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we simulate all possible moves Alice and Bob can make, calculating the total stones each player can collect. We explore every possible combination of moves to determine if Alice can secure more stones than Bob. The optimal Optimal Solution approach improves this to O(n²).

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

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

What are the interview tips for Stone Game?

Always clarify the rules of the game to ensure you understand the optimal strategies. Think about how you can break down the problem into smaller subproblems, especially for dynamic programming. Practice explaining your thought process out loud, as this will help you articulate your approach during interviews.

What are common mistakes when solving Stone Game?

Not considering both players play optimally, leading to incorrect assumptions about possible outcomes. Failing to account for the recursive nature of the problem in the brute force approach.

#877

Stone Game

Medium

ArrayMathDynamic ProgrammingGame 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²)

The optimal solution leverages dynamic programming to avoid redundant calculations. We use a DP table to store the maximum stones Alice can collect from any subarray of piles, ensuring we only compute each state once.

⚙️

Algorithm

3 steps

1Step 1: Create a DP table where dp[i][j] represents the maximum stones Alice can collect from piles[i] to piles[j].
2Step 2: Initialize the table for single piles, where dp[i][i] = piles[i].
3Step 3: Fill the table for larger subarrays using the relation: dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]).

solution.py10 lines

1def stoneGame(piles):
2    n = len(piles)
3    dp = [[0] * n for _ in range(n)]
4    for i in range(n):
5        dp[i][i] = piles[i]
6    for length in range(2, n + 1):
7        for i in range(n - length + 1):
8            j = i + length - 1
9            dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
10    return dp[0][n - 1] > 0

ℹ

Complexity note: The time complexity remains O(n²) because we fill a DP table of size n x n. The space complexity is also O(n²) due to the storage of the DP table.

1Alice can always win if both play optimally due to the even number of piles.
2The game can be analyzed using dynamic programming to optimize decision-making.

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