Skip to main content
Talentd

Stone Game II - Solution & Explanation

MediumArrayMathDynamic ProgrammingPrefix Sum20 min readAsked at: Amazon, Meta, Uber +2
Practice this problem

Problem Statement

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X). Initially, M = 1.

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

 

Example 1:

Input: piles = [2,7,9,4,4]

Output: 10

Explanation:

  • If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 stones in total.
  • If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 stones in total.

So we return 10 since it's larger.

Example 2:

Input: piles = [1,2,3,4,5,100]

Output: 104

 

Constraints:

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 104

Approach Overview

Problem Overview: You are given an array of piles where each element represents stones in that pile. Two players take turns taking the first X piles where 1 ≤ X ≤ 2M, and M updates to max(M, X) after each move. Both players play optimally. The goal is to compute the maximum stones Alice (the first player) can collect.

Approach 1: Dynamic Programming with Memoization (O(n^3) time, O(n^2) space)

This is a classic optimal-play problem from game theory. Define a state dp(i, M) representing the maximum stones the current player can obtain starting from pile index i with parameter M. For each state, try taking X piles where 1 ≤ X ≤ 2M. After taking those piles, the opponent plays optimally, so your gain equals totalRemaining - dp(i + X, max(M, X)). Precompute suffix or prefix sums using prefix sums so the remaining stones can be calculated in O(1). Memoization stores results for each (i, M) pair to avoid recomputation. There are roughly O(n^2) states and up to 2M transitions per state, giving O(n^3) time.

Approach 2: Bottom-Up Dynamic Programming (O(n^3) time, O(n^2) space)

The same state transition can be implemented iteratively. Create a DP table where dp[i][M] stores the maximum stones the current player can collect from index i. Iterate indices from the end of the array toward the start because future states depend on later piles. For each state, evaluate every possible X choice in the range 1..2M. Use a precomputed suffix sum so you can instantly compute the total remaining stones and subtract the opponent's optimal result. Bottom-up DP avoids recursion overhead and can be easier to reason about during debugging, though the asymptotic complexity remains O(n^3).

Recommended for interviews: The memoized top-down dynamic programming solution is the most common interview answer. It shows you recognize the problem as a minimax-style DP and know how to model states with (index, M). Starting with the recursive formulation demonstrates understanding of the game strategy, while memoization reduces exponential exploration to polynomial time. If time allows, converting the same recurrence to bottom-up DP shows deeper mastery of dynamic programming state transitions.

Approach 1: Dynamic Programming with Memoization

In this approach, the problem is viewed as a decision-making process for Alice, where she wants to maximize her stones given Bob will try his best to minimize them. We can use Dynamic Programming (DP) to remember the maximum stones Alice can get from any position with a given M value.

The state dp[i][M] represents the maximum stones Alice can get starting from the i-th pile with a given M.

  • For each state, Alice can take X = 1 to X = 2M piles.
  • We iterate over every possibility for X to compute the best outcome.
  • We keep track of the current total stones taken up to the i-th pile, which helps to quickly calculate the stones Alice can take if she chooses X piles.
  • This is computed recursively with memoization to improve efficiency.

This Python solution uses a recursive helper function with memoization to store and reuse results for subproblems. It calculates Alice's optimal score by considering all possibilities of taking piles, updating the maximum number of stones Alice can secure.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time Complexity: O(n3) due to two nested loops over the pile range and repeated evaluation of states.
Space Complexity: O(n2) for storing computed states in the memoization table.

Try this approach in the editor →

Approach 2: Bottom-Up Dynamic Programming

A direct iterative solution (Non-memoization) that uses Dynamic Programming to build the solution from smaller subproblems towards larger problems. We create an array dp[i][M] where each entry records the maximum stones Alice can get starting at position i with parameter M. This approach calculates every step systematically, using previously solved smaller cases.

  • Initialize the array starting from the last pile and moving backward.
  • For each state dp[i][M], calculate the possible maximum value by considering taking 1 to 2M piles in each iteration.

This C solution uses a bottom-up approach with prefix sums to rapidly compute the sum of stones from any position onward. It fills up a DP table where each cell provides the best decision possible. The primary loop fills these using iterative tuning.

Code

CC++C#

C

C++

C#

Complexity

Time Complexity: O(n3), iterating over each subproblem space.
Space Complexity: O(n2) for the DP table tracking best decisions.

Try this approach in the editor →

Approach 3: Prefix Sum + Memoization Search

Since the player can take all the stones from the first X piles each time, that is, they can take the stones from an interval, we can first preprocess a prefix sum array s of length n+1, where s[i] represents the sum of the first i elements of the array piles.

Then we design a function dfs(i, m), which represents the maximum number of stones that the current player can take when they can start from index i of the array piles, and the current M is m. Initially, Alice starts from index 0, and M=1, so the answer we need to find is dfs(0, 1).

The calculation process of the function dfs(i, m) is as follows:

  • If the current player can take all the remaining stones, the maximum number of stones they can take is s[n] - s[i];
  • Otherwise, the current player can take all the stones from the first x piles of the remaining ones, where 1 leq x leq 2m, and the maximum number of stones they can take is s[n] - s[i] - dfs(i + x, max(m, x)). That is to say, the number of stones that the current player can take is the number of all the remaining stones minus the number of stones that the opponent can take in the next round. We need to enumerate all x, and take the maximum value as the return value of the function dfs(i, m).

To avoid repeated calculations, we can use memoization search.

Finally, we return dfs(0, 1) as the answer.

The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the length of the array piles.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

Python

Python

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Memoization

Time Complexity: O(n3) due to two nested loops over the pile range and repeated evaluation of states.
Space Complexity: O(n2) for storing computed states in the memoization table.

Bottom-Up Dynamic Programming

Time Complexity: O(n3), iterating over each subproblem space.
Space Complexity: O(n2) for the DP table tracking best decisions.

Prefix Sum + Memoization Search—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with MemoizationO(n^3)O(n^2)Best for interviews. Natural recursive formulation with caching of (index, M) states.
Bottom-Up Dynamic ProgrammingO(n^3)O(n^2)Useful when recursion depth is a concern or when implementing iterative DP tables.

Video Solution

Stone Game II - Leetcode 1140 - Python • NeetCodeIO • 32,434 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Stone Game II easy or hard?
Stone Game II is rated Medium on LeetCode but feels closer to upper‑medium difficulty. The challenge is identifying the correct DP state and understanding that the current player's gain equals total remaining stones minus the opponent's optimal result.
Stone Game II Python/Java solution
Python and Java solutions typically implement a recursive DP function with memoization. The function dp(i, M) tries all X values from 1 to 2M, calculates the stones taken using suffix sums, and subtracts the opponent's optimal result. Memoization ensures each state is computed only once.
How to solve Stone Game II in O(n)?
Stone Game II generally cannot be solved in O(n) because the optimal strategy depends on exploring many possible move sizes. The accepted solution uses dynamic programming with states (index, M), leading to O(n^3) time in the straightforward implementation. Some optimizations reduce constants but the complexity remains polynomial.
What is the best approach for Stone Game II?
Dynamic Programming with memoization is the standard approach. Model the game state as (index, M) where index is the current pile and M controls how many piles can be taken. For each move, try X piles where 1 ≤ X ≤ 2M and subtract the opponent's optimal result. With prefix or suffix sums, the solution runs in O(n^3) time and O(n^2) space.
Is Stone Game II asked at Google/Amazon/Meta?
Stone Game II represents a common interview pattern involving game theory and dynamic programming. Variations of optimal-play stone games frequently appear in interviews at companies like Amazon, Google, and Meta because they test DP state design and reasoning about opponent moves.
What data structure is used in Stone Game II?
The main structure is a 2D dynamic programming table or memoization cache storing results for (index, M) states. Prefix sums or suffix sums are also used to compute the total remaining stones in constant time during transitions.
What is the time complexity of Stone Game II?
The typical dynamic programming solution runs in O(n^3) time and O(n^2) space. There are about O(n^2) states defined by (index, M), and each state explores up to 2M choices. Using prefix or suffix sums ensures each transition calculates remaining stones in O(1).

Ready to solve this problem?

Practice Stone Game II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Stone Game IX

Next

Stone Game V