Skip to main content

877. Stone Game

medium

Alice and Bob alternate taking stones from either end of a row of piles; both play optimally. Classic interval game DP: dp[i][j] = best score the current player can achieve over the gap (j - i).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = score difference (current player's stones minus opponent's stones) when the game is played optimally on piles[i..j].

Hint 2

dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]).

Hint 3

Answer = dp[0][n-1] > 0.

Hint 4

Mathematical shortcut: with an even pile count and odd total, Alice can always win by picking either all even-indexed or all odd-indexed piles — always return true. But interviewers want to see the DP.

Solution approach

Reveal approach

Interval DP on score difference. dp[i][j] is the maximum (currentPlayer - opponent) score the player to move can achieve on piles[i..j]. Recurrence: the current player chooses the left or right end. If they pick piles[i], they gain piles[i] and the opponent plays optimally on piles[i+1..j], yielding piles[i] - dp[i+1][j]. Similarly for the right end. So dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]). Base case: dp[i][i] = piles[i]. Fill in increasing interval length. Alice wins iff dp[0][n-1] > 0. There is a parity argument (with even pile count and odd total Alice always wins) but the DP generalizes to variants that break the shortcut.

Complexity

Time
O(n^2)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • interval-dp
  • game-theory

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Stone Game and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →