Skip to main content
Talentd

Stone Game - Solution & Explanation

MediumArrayMathDynamic ProgrammingGame Theory26 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

Alice and Bob play a game with piles of stones. There are an even 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. The total number of stones across all the piles is odd, so there are no ties.

Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.

 

Example 1:

Input: piles = [5,3,4,5]
Output: true
Explanation: 
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.

Example 2:

Input: piles = [3,7,2,3]
Output: true

 

Constraints:

  • 2 <= piles.length <= 500
  • piles.length is even.
  • 1 <= piles[i] <= 500
  • sum(piles[i]) is odd.

Approach Overview

Problem Overview: You are given an array piles where each element represents stones in a pile. Two players (Alex and Lee) take turns removing a pile from either the start or end of the array. Both play optimally. The goal is to determine whether Alex, who moves first, can guarantee more stones than Lee.

Approach 1: Greedy / Game Theory Insight (O(n) time, O(1) space)

The key observation comes from game theory. The number of piles is even, so Alex can choose to always pick from either the even-indexed or odd-indexed piles. Before the game begins, compute the total stones in even positions and odd positions. One of these groups must have a larger sum. On the first move, Alex chooses the side that corresponds to the higher-sum parity and then continues forcing Lee to take from the opposite parity. Because Alex controls the parity choice from the first move, Alex can always collect the larger half of piles. Implementation simply returns true. Iteration over the array to reason about parity takes O(n) time with constant O(1) space.

Approach 2: Dynamic Programming (Minimax Difference) (O(n^2) time, O(n^2) space)

A more general solution models the game using dynamic programming. Define dp[i][j] as the maximum score difference the current player can achieve over the opponent using piles between indices i and j. When choosing the left pile, the resulting advantage becomes piles[i] - dp[i+1][j]. When choosing the right pile, it becomes piles[j] - dp[i][j-1]. Store the better of the two options. Build the table from smaller subarrays to larger ones. If dp[0][n-1] > 0, the first player ends with more stones. This approach systematically evaluates optimal play and is a standard technique for interval games involving arrays. Time complexity is O(n^2) because every subarray is evaluated, and the DP table requires O(n^2) space.

Recommended for interviews: The dynamic programming formulation demonstrates strong problem-solving skills and understanding of minimax-style games. Many interviewers expect candidates to derive the dp[i][j] recurrence first. After recognizing the constraints (even number of piles), the greedy game-theory insight shows deeper reasoning and leads to the optimal constant-space solution.

Approach 1: Greedy Approach

This approach uses a straightforward observation: since Alice starts first and can always choose the better pile (since the number of piles is even and both play optimally), Alice will always have the advantage. Thus, Alice can always ensure she ends up with more stones than Bob by always picking the piles in a manner that maximizes her total stones. Therefore, the solution can be returned directly as true without sophisticated calculations.

In Python, this solution directly returns True as the outcome based on the problem constraints and the fact that Alice will always win with optimal moves.

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

Time Complexity: O(1) - The solution involves a direct return statement.
Space Complexity: O(1) - No additional space is used.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

The dynamic programming approach involves calculating the maximum stones a player can gather from any given state, thus determining the optimal strategy. We can define a DP table where dp[i][j] represents the maximum number of stones a player can get from piles i to j inclusive. The formula to update the DP table is determined by considering the take from left or right scenarios. In the end, Alice wins if dp[0][n-1] is greater than half of the total stones, ensuring her strategy leads to a win.

This Python solution defines a DP table to track maximum stones collected from segments. Through iteration, it populates the table considering optimal decisions at each step. Alice wins if she collects more stones, represented by a positive score in dp[0][n-1].

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

Time Complexity: O(n^2) - We fill an n by n table.
Space Complexity: O(n^2) - Additional space for the table.

Try this approach in the editor →

Approach 3: Memoization Search

We design a function dfs(i, j) that represents the maximum difference in the number of stones between the current player and the other player when considering piles from the i-th to the j-th. The answer is then dfs(0, n - 1) \gt 0.

The function dfs(i, j) is computed as follows:

  • If i \gt j, there are no stones left, so the current player cannot take any stones and the difference is 0, i.e., dfs(i, j) = 0.
  • Otherwise, the current player has two choices: if they take the i-th pile, the difference between the current player and the other player is piles[i] - dfs(i + 1, j); if they take the j-th pile, the difference is piles[j] - dfs(i, j - 1). The current player will choose the option with the larger difference, so dfs(i, j) = max(piles[i] - dfs(i + 1, j), piles[j] - dfs(i, j - 1)).

Finally, we only need to check whether dfs(0, n - 1) \gt 0.

To avoid redundant computation, we can use memoization: we use an array f to record all values of dfs(i, j), so that when the function is called again, we can directly retrieve the answer from f without recomputing.

The time complexity is O(n^2) and the space complexity is O(n^2), where n is the number of stone piles.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Dynamic Programming

We can also use dynamic programming. Define f[i][j] as the maximum difference in the number of stones the current player can obtain over the other player from piles piles[i..j]. The final answer is then f[0][n - 1] \gt 0.

Initially, f[i][i] = piles[i], because with only one pile, the current player can only take that pile, and the difference is piles[i].

For f[i][j] where i \lt j, there are two cases:

  • If the current player takes pile piles[i], the remaining piles are piles[i + 1..j], and it becomes the other player's turn, so f[i][j] = piles[i] - f[i + 1][j].
  • If the current player takes pile piles[j], the remaining piles are piles[i..j - 1], and it becomes the other player's turn, so f[i][j] = piles[j] - f[i][j - 1].

Therefore, the final state transition equation is f[i][j] = max(piles[i] - f[i + 1][j], piles[j] - f[i][j - 1]).

Finally, we only need to check whether f[0][n - 1] \gt 0.

The time complexity is O(n^2) and the space complexity is O(n^2), where n is the number of stone piles.

Similar problems:

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(1) - The solution involves a direct return statement.
Space Complexity: O(1) - No additional space is used.

Dynamic Programming Approach

Time Complexity: O(n^2) - We fill an n by n table.
Space Complexity: O(n^2) - Additional space for the table.

Memoization Search—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy / Game Theory InsightO(n)O(1)Best for this exact problem since the number of piles is even and optimal play guarantees Alex wins.
Dynamic Programming (Minimax Difference)O(n^2)O(n^2)General solution for two-player optimal interval games where parity tricks or mathematical shortcuts are not obvious.

Video Solution

Stone Game - Leetcode 877 - Python • NeetCode • 44,410 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Stone Game easy or hard?
Stone Game is rated Medium on LeetCode but feels easier once the game theory insight is discovered. Without the observation about even piles, the problem naturally leads to a dynamic programming minimax solution with O(n^2) complexity.
Stone Game Python/Java solution
In Python or Java, the greedy solution can be implemented in one line by returning true because Alex always wins with optimal play. The DP solution builds a 2D array where dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) and checks whether dp[0][n-1] is positive.
How to solve Stone Game in O(n)?
Use the parity insight. With an even number of piles, Alex can decide on the first move whether to collect stones from even or odd indices. After that, every move forces Lee into the opposite parity. By choosing the parity with the larger total sum, Alex guarantees the final score advantage in O(n) time.
What is the best approach for Stone Game?
The optimal solution uses a game theory observation: since the number of piles is even, Alex can always choose either even-indexed or odd-indexed piles and force Lee to take the other set. By picking the parity with the larger total sum, Alex guarantees a win. This leads to an O(n) time and O(1) space solution that simply returns true.
Is Stone Game asked at Google/Amazon/Meta?
Stone Game–style problems appear frequently in interviews at companies like Amazon, Google, and Meta when testing dynamic programming and game theory reasoning. Interviewers often expect candidates to first derive the interval DP solution before recognizing the mathematical shortcut.
What data structure is used in Stone Game?
The dynamic programming solution uses a 2D DP table dp[i][j] to store the score difference for each subarray. The greedy solution relies only on array indexing and parity reasoning, so it uses constant additional memory.
What is the time complexity of Stone Game?
The greedy game-theory solution runs in O(n) time with O(1) extra space because it only reasons about the parity of indices. The dynamic programming approach evaluates every subarray state dp[i][j], resulting in O(n^2) time and O(n^2) space.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Stone Game IX

Next

Stone Game V