Watch 10 video solutions for Stone Game, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by NeetCode has 42,065 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 500piles.length is even.1 <= piles[i] <= 500sum(piles[i]) is odd.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 | Time | Space | When to Use |
|---|---|---|---|
| Greedy / Game Theory Insight | O(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. |