algoadvance

Leetcode 877. Stone Game

Problem Statement

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 up with the most stones. The total number of stones 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 from either the beginning or the end of the row. This continues until there are no more piles left, at which point the player with the most stones wins.

Given an array piles where piles[i] is the number of stones in the i-th pile, return True if Alice wins the game (assuming both play optimally), otherwise return False.

Example:

• Input: piles = [5,3,4,5]
• Output: True

Clarifying Questions

1. What is the minimum and maximum length of the piles array?
2. Can the values within the piles array be very large?
3. Should we consider edge cases such as arrays with minimum length (e.g., 2 piles)?
4. Does the array always have an even number of elements? (As stated in the problem, this is true.)

Strategy

This problem can be approached using dynamic programming, but we can also leverage a mathematical insight because:

• The total number of piles is even.
• The sum of the stones is odd.

Since Alice always starts first, she can choose any strategy that makes her win. Given that there is no possibility of a tie (since the total number of stones is odd), mathematically, Alice can always win if both players play optimally. This can be reasoned because she could always choose piles in a way that leaves Bob with disadvantageous positions.

Thus, the solution boils down to returning True without actually simulating the game, as Alice can always win based on problem constraints.

Let’s also provide the dynamic programming approach (if necessary), as follows.

Dynamic Programming Strategy

1. Create a DP array dp where dp[i][j] represents the maximum stones a player can get more than the opponent from the subarray piles[i...j].
2. Recurrence relation:

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

   This means the player can choose the left end or right end and will take that pile minus the opponent’s best future result.

Code

public class StoneGame {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        
        // Fill the base cases: if there's only one pile, the player takes it
        for (int i = 0; i < n; ++i) {
            dp[i][i] = piles[i];
        }
        
        // Fill the rest of dp
        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i < n - length + 1; ++i) {
                int j = i + length - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        
        return dp[0][n - 1] > 0;
    }
    
    public static void main(String[] args) {
        StoneGame sg = new StoneGame();
        int[] piles = {5, 3, 4, 5};
        System.out.println(sg.stoneGame(piles));  // Output: True
    }
}

Time Complexity

• The time complexity of filling the DP table is O(n^2) where n is the number of piles.
• The space complexity is also O(n^2) for the DP table.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?