Scale Engineer

Stone Game

Med
#0831Time: O(2^n), where n is the number of piles. For each subproblem, we make two recursive calls, leading to an exponential number of operations.Space: O(n), where n is the number of piles. This is due to the maximum depth of the recursion call stack.1 company
Patterns
MathDynamic ProgrammingGame Theory
Data structures
Array
Companies
Cisco

Prompt

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.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach models the game using a recursive function that represents the choices of the current player. At each step, a player chooses the pile that maximizes their final score relative to the opponent. This is a classic minimax strategy. The function calculates the maximum score difference the current player can achieve from a given sub-array of piles.

Algorithm

  • Create a recursive helper function solve(piles, i, j) that returns the maximum score difference a player can get from piles i to j.
  • Base Case: If i == j, there's only one pile left. The current player takes it, so return piles[i].
  • Recursive Step: The current player has two choices:
    1. Take piles[i]: Their score difference will be piles[i] minus the score difference the next player gets from the remaining piles [i+1, j]. This is piles[i] - solve(piles, i + 1, j).
    2. Take piles[j]: Similarly, the score difference is piles[j] - solve(piles, i, j - 1).
  • The player chooses the move that maximizes their score difference. So, solve(i, j) returns max(choice1, choice2).
  • The initial call is solve(piles, 0, piles.length - 1). Alice wins if this result is greater than 0.

Walkthrough

We define a recursive function, say solve(i, j), which returns the maximum score difference the current player can obtain from the piles in the range [i, j]. The current player can either take piles[i] or piles[j]. If the player takes piles[i], their score increases by piles[i]. The opponent will then play on the subproblem [i+1, j] and will get a score difference of solve(i+1, j). So, the current player's net score difference from this move is piles[i] - solve(i+1, j). Similarly, if the player takes piles[j], their net score difference is piles[j] - solve(i, j-1). Since the player plays optimally, they will choose the move that maximizes their score difference. The initial call is solve(0, n-1). Alice wins if this value is greater than 0. This approach recomputes the same subproblems multiple times, leading to an exponential time complexity.

class Solution {    public boolean stoneGame(int[] piles) {        return solve(piles, 0, piles.length - 1) > 0;    }     private int solve(int[] piles, int i, int j) {        if (i == j) {            return piles[i];        }                int takeFirst = piles[i] - solve(piles, i + 1, j);        int takeLast = piles[j] - solve(piles, i, j - 1);                return Math.max(takeFirst, takeLast);    }}

Complexity

Time

O(2^n), where n is the number of piles. For each subproblem, we make two recursive calls, leading to an exponential number of operations.

Space

O(n), where n is the number of piles. This is due to the maximum depth of the recursion call stack.

Trade-offs

Pros

  • Conceptually simple and directly translates the game's rules into code.

  • Serves as a good foundation for more optimized dynamic programming solutions.

Cons

  • Extremely inefficient due to a large number of redundant calculations for the same subproblems.

  • Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial input sizes.

Solutions

class Solution {public  boolean stoneGame(int[] piles) {    int n = piles.length;    int[][] f = new int[n][n];    for (int i = 0; i < n; ++i) {      f[i][i] = piles[i];    }    for (int i = n - 2; i >= 0; --i) {      for (int j = i + 1; j < n; ++j) {        f[i][j] = Math.max(piles[i] - f[i + 1][j], piles[j] - f[i][j - 1]);      }    }    return f[0][n - 1] > 0;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem