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.
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.
Time Complexity: O(1) - The solution involves a direct return statement.
Space Complexity: O(1) - No additional space is used.
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].
Time Complexity: O(n^2) - We fill an n by n table.
Space Complexity: O(n^2) - Additional space for the table.
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:
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.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.
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:
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].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:
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(1) - The solution involves a direct return statement. |
| Dynamic Programming Approach | Time Complexity: O(n^2) - We fill an n by n table. |
| Memoization Search | — |
| Dynamic Programming | — |
| 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. |
Stone Game - Leetcode 877 - Python • NeetCode • 42,065 views views
Watch 9 more video solutions →Practice Stone Game with our built-in code editor and test cases.
Practice on FleetCode