Stone Game

#512 Most AskedMedium

Stone Game #512 Most Asked

Medium

6 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the `piles` array, and what is the range of values for the integers within the array?
Can the `piles` array be empty or null? If so, what should I return?
Is the number of piles always an even number, or could it be odd?
Are we concerned with the absolute score, or just determining if Alex's score is greater than Lee's score?
Is there a specific return type I should use if Alex wins (e.g., boolean, or should I calculate the exact score difference)?

Brute Force Solution

Approach

In the Stone Game, we want to see if the first player can always win by picking stones optimally. The brute force approach explores every possible sequence of stone selections that both players could make, essentially simulating all possible games.

Here's how the algorithm would work step-by-step:

Imagine each player takes turns picking either the first or last stone from the row.
Start by having the first player pick the first stone. Then, consider all possible moves the second player could make in response.
Now, for each of those scenarios, consider all the possible moves the first player could make next, and so on.
Keep doing this, exploring all possible game scenarios until all the stones are gone.
For each complete game, calculate the total score for the first player and the second player.
If, in every possible game scenario, the first player's score is higher than the second player's score, then the first player can always win.
Otherwise, if there is even one game scenario where the second player wins or ties, then the first player cannot always guarantee a win.

Code Implementation

def stone_game_brute_force(pile_of_stones):
    def can_first_player_win(stones, first_player_score, second_player_score, turn):
        if not stones:
            # All stones have been taken, check scores
            return first_player_score > second_player_score

        if turn == 0:
            # First player's turn
            
            # Try taking the first stone
            win_if_take_first = can_first_player_win(
                stones[1:], first_player_score + stones[0], second_player_score, 1
            )
            
            # Try taking the last stone
            win_if_take_last = can_first_player_win(
                stones[:-1], first_player_score + stones[-1], second_player_score, 1
            )
            
            # First player wins if they win in all game scenarios
            return win_if_take_first and win_if_take_last
        else:
            # Second player's turn
            
            # Try taking the first stone
            win_if_take_first = can_first_player_win(
                stones[1:], first_player_score, second_player_score + stones[0], 0
            )
            
            # Try taking the last stone
            win_if_take_last = can_first_player_win(
                stones[:-1], first_player_score, second_player_score + stones[-1], 0
            )

            # If second player can always win return false
            return win_if_take_first and win_if_take_last

    # The first player wants to maximize their score.
    return can_first_player_win(pile_of_stones, 0, 0, 0)

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible game scenarios by recursively simulating each player's choices. At each step, a player chooses either the first or last stone, leading to two possible branches in the decision tree. Since there are n stones, this branching occurs up to n times, resulting in a binary tree with a depth of n. Therefore, the total number of possible games is approximately 2^n. Thus, the time complexity is O(2^n).

Space Complexity

O(2^N) – The brute force approach explores all possible game scenarios. This exploration is done through recursion. At each level of recursion, a choice is made between picking the first or last stone. Since there are N stones initially, the maximum depth of the recursion tree can be N. Because each level can branch into two possibilities (pick left or right), the total number of possible game scenarios that are explored can be 2^N. Therefore, the recursion stack can grow up to a height of N, and the number of branches is determined by the number of game scenarios, so the space complexity is O(2^N), representing the number of game scenarios explored by the algorithm.

Optimal Solution

Approach

The core idea is to recognize that each player aims to maximize their own score, assuming perfect play from both. This problem can be efficiently solved using a technique that remembers the best possible outcome for each section of the stones.

Here's how the algorithm would work step-by-step:

Realize that the first player can always win if they play optimally.
To determine how much better the first player's score will be, work backward from the end of the game.
Consider smaller sections of the stones and determine the best possible score difference for the first player in those sections.
Use those smaller results to build up to the bigger sections, always choosing the move that gives the first player the highest possible advantage.
By breaking the problem down like this, we avoid needing to explore all the possible moves and counter-moves.

Code Implementation

def stone_game(piles):
    number_of_piles = len(piles)

    # dp[i][j] stores the max advantage Alice can get from piles[i...j]
    dynamic_programming_table = [[0] * number_of_piles for _ in range(number_of_piles)]

    # Base case: single pile, Alice takes it
    for i in range(number_of_piles):
        dynamic_programming_table[i][i] = piles[i]

    # Fill the table diagonally
    for pile_length in range(2, number_of_piles + 1):
        for i in range(number_of_piles - pile_length + 1):
            j = i + pile_length - 1

            # Alice chooses either the left or right pile
            dynamic_programming_table[i][j] = max(
                piles[i] - dynamic_programming_table[i + 1][j],
                piles[j] - dynamic_programming_table[i][j - 1]
            )

    # Alice wins if her advantage is positive
    # Determine who wins and return
    return dynamic_programming_table[0][number_of_piles - 1] > 0

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. The outer loop determines the length of the subarray, ranging from 2 to n. The inner loop iterates through all possible starting positions for a subarray of that length. Therefore, the algorithm essentially calculates the optimal score for each subarray, and there are approximately n * n/2 such subarrays. This results in a time complexity of O(n²).

Space Complexity

O(N^2) – The solution uses dynamic programming to store the best possible score difference for each section of the stones. This involves creating a table (or memoization structure) to store these intermediate results. Since we're considering all possible sub-sections of the stones, the size of this table grows quadratically with the number of stones. Therefore, the auxiliary space used is proportional to N^2, where N is the number of stones.

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as no stones can be taken.
Array with only one pile	Alex takes the only pile, so return true.
Array with two piles	Alex takes the larger pile; return true as Alex always wins with two piles.
Array with all piles having the same number of stones	Alex can still force a win if the total number of piles is odd, otherwise Lee can force a draw; calculate based on array length.
Array with a single very large pile compared to other small piles	Alex will take the large pile and try to maximize their gain; the optimal strategy must be calculated.
Large input array (performance)	Use dynamic programming to avoid exponential time complexity from naive recursion.
Integer overflow when summing pile values	Use long data type to store sums to prevent potential integer overflow.
Negative number of stones in a pile (invalid input)	Throw an IllegalArgumentException or return false, depending on problem specification.

Null or empty input array

How to Handle:

Return false immediately as no stones can be taken.

Array with only one pile

How to Handle:

Alex takes the only pile, so return true.

Array with two piles

How to Handle:

Alex takes the larger pile; return true as Alex always wins with two piles.

Array with all piles having the same number of stones

How to Handle:

Alex can still force a win if the total number of piles is odd, otherwise Lee can force a draw; calculate based on array length.

Array with a single very large pile compared to other small piles

How to Handle:

Alex will take the large pile and try to maximize their gain; the optimal strategy must be calculated.

Large input array (performance)

How to Handle:

Use dynamic programming to avoid exponential time complexity from naive recursion.

Integer overflow when summing pile values

How to Handle:

Use long data type to store sums to prevent potential integer overflow.

Negative number of stones in a pile (invalid input)

How to Handle:

Throw an IllegalArgumentException or return false, depending on problem specification.