Stone Game 2

Problem

Alice and Bob continue their games with piles of stones.  There are a 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. 

Alice and Bob take turns, with Alice starting first.  Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Examples

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

Example 2:

Input: piles = [1,2,3,4,5,100]
Output: 104

Solution

Method 1 - By minimizing the stones returned by Bob

The game involves Alice and Bob playing optimally to collect as many stones as possible from a row of piles. Alice always plays first, and the players take turns. The key constraints are:

1. Each player can take any number of piles between 1 and 2M, where M is initially set to 1 and adjusts based on the moves.

2. The goal is to maximize the number of stones collected by Alice.

3. Prefix Sums:

   • We use prefixSums to quickly calculate the sum of stones from any subarray.
   • prefixSums[i] stores the total number of stones from the start up to the i-th pile.

4. Memoization Table:

   • memo[i][M] stores the maximum number of stones Alice can collect starting from index i with the parameter M.
   • This avoids recalculating results for the same state multiple times.

5. Recursive Function:

   • The helper function findMaxStones handles the game logic recursively.
   • It ensures that both players play optimally, and calculates Alice's maximum possible stones.

This is how recursion will work:

• The goal is to maximize Alice's collected stones. For each possible number of piles X Alice can take (from 1 to 2 * M):
  • Calculate the total stones Alice can collect by summing the stones from index i to i + X - 1.
  • Recursively compute the result for the remaining piles starting from index i + X, and adjust M to max(M, X).
  • Deduct the maximum stones Bob can collect in his turn from the total stones Alice can collect.

Video Explanation

Here is the video explanation: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/6FAb-ZFGylM" frameborder="0" allowfullscreen></iframe></div>

Code

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> piles;
    vector<int> prefixSums;
    int n;
    vector<vector<int>> memo;

    int stoneGameII(vector<int>& piles_) {
        piles = piles_;
        n = piles.size();
        memo.assign(n, vector<int>(n + 1, -1));

        prefixSums.assign(n + 1, 0);
        for (int i = 0; i < n; ++i) prefixSums[i + 1] = prefixSums[i] + piles[i];

        return findMaxStones(0, 1);
    }

private:
    int findMaxStones(int i, int M) {
        if (i >= n) return 0;
        if (memo[i][M] != -1) return memo[i][M];
        int maxStones = 0;
        for (int X = 1; X <= 2 * M && i + X <= n; ++X) {
            int currentStones = prefixSums[i + X] - prefixSums[i];
            int totalStonesRemaining = prefixSums[n] - prefixSums[i + X];
            int nextStones = findMaxStones(i + X, max(M, X));
            maxStones = max(maxStones, currentStones + totalStonesRemaining - nextStones);
        }
        memo[i][M] = maxStones;
        return maxStones;
    }
};

Java

class Solution {
    private  int[] piles;
    private int[] prefixSums;
    private int n;
    private int[][] memo;
    public int stoneGameII(int[] piles) {
        this.piles = piles;
        this.n = piles.length;
        this.memo = new int[n][n + 1];

        // Initialize memo table to -1 indicating uncomputed states
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        // Calculate prefix sums
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + piles[i];
        }
        this.prefixSums = prefixSums;
        return findMaxStones(0, 1);
    }

    private int findMaxStones(int i, int M) {
        if (i >= n) {
            return 0;
        }

        if (memo[i][M] != -1) {
            return memo[i][M];
        }

        int maxStones = 0;
        int total = 0;

        for (int X = 1; X <= 2 * M && i + X <= n; X++) {
             // Using prefix sums to calculate the sum of stones taken by Alice
             int currentStones = prefixSums[i + X] - prefixSums[i];
             int totalStonesRemaining = prefixSums[n] - prefixSums[i + X];
             // The result of the remaining game
             int nextStones = findMaxStones(i + X, Math.max(M, X));
             
             // Alice's optimal stones after Bob's turn
             maxStones = Math.max(maxStones, currentStones + totalStonesRemaining - nextStones);
        }

        memo[i][M] = maxStones;
        return maxStones;
    }
}

Python

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        memo = [[-1] * (n + 1) for _ in range(n)]
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + piles[i]

        def find_max_stones(i: int, M: int) -> int:
            if i >= n:
                return 0
            if memo[i][M] != -1:
                return memo[i][M]
            max_stones = 0
            for X in range(1, min(2*M, n - i) + 1):
                current = prefix[i+X] - prefix[i]
                total_remaining = prefix[n] - prefix[i+X]
                next_stones = find_max_stones(i+X, max(M, X))
                max_stones = max(max_stones, current + total_remaining - next_stones)
            memo[i][M] = max_stones
            return max_stones

        return find_max_stones(0, 1)

Complexity

• Time: O(n^3)
  • Because at each recursive call, i goes from 0 to n
  • But another parameter is m and in worst case it can go to n/2
  • Then, we are running the inner loop insider function from X = 1 to n in worst case
• Space: O(n^2) using recursion stack and memo table

Method 2 - By maximizing the difference

Intuition & Approach

• Treat the game as zero-sum and compute the maximum difference the current player can achieve over the opponent from state (i, M).
• Let diff(i, M) be the maximum (current_player_stones - opponent_stones) obtainable starting at index i with parameter M.
• If the current player takes X piles (1 ≤ X ≤ 2M) they collect sum(i, i+X-1), then the remaining game's value for the opponent is diff(i+X, max(M, X)). So the net gain is sum(i,i+X-1) - diff(i+X, max(M,X)).
• Recurrence: diff(i, M) = max_{1<=X<=2M && i+X<=n} ( sum(i,i+X-1) - diff(i+X, max(M,X)) ), with diff(i, M) = 0 when i >= n.
• After computing maxDiff = diff(0,1), use Alice - Bob = maxDiff and Alice + Bob = total to solve for Alice: Alice = (total + maxDiff) / 2.
• Use memoization over states (i, M) to achieve the stated complexity.

Code

C++

#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

class Solution {
public:
    vector<int> piles;
    vector<int> prefixSums;
    int n;
    vector<vector<int>> memo;

    int stoneGameII(vector<int>& piles_) {
        piles = piles_;
        n = piles.size();
        memo.assign(n, vector<int>(n + 1, numeric_limits<int>::min()));
        prefixSums.assign(n + 1, 0);
        for (int i = 0; i < n; ++i) prefixSums[i + 1] = prefixSums[i] + piles[i];
        int maxDifference = findMaxDifference(0, 1);
        int totalStones = prefixSums[n];
        return (totalStones + maxDifference) / 2;
    }

private:
    int findMaxDifference(int i, int M) {
        if (i >= n) return 0;
        if (memo[i][M] != numeric_limits<int>::min()) return memo[i][M];
        int maxDiff = numeric_limits<int>::min();
        for (int X = 1; X <= 2 * M && i + X <= n; ++X) {
            int currentStones = prefixSums[i + X] - prefixSums[i];
            int nextDiff = findMaxDifference(i + X, max(M, X));
            maxDiff = max(maxDiff, currentStones - nextDiff);
        }
        memo[i][M] = maxDiff;
        return maxDiff;
    }
};

Java

public class Solution {
    private int[] piles;
    private int[] prefixSums;
    private int n;
    private int[][] memo;

    public int stoneGameII(int[] piles) {
        this.piles = piles;
        this.n = piles.length;
        this.memo = new int[n][n + 1];

        // Initialize memo table to Integer.MIN_VALUE indicating uncomputed
        // states
        for (int[] row : memo) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }

        // Calculate prefix sums
        this.prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + piles[i];
        }

        // Calculate the maximum difference between Alice's and Bob's stones,
        // starting at index 0 with M = 1
        int maxDifference = findMaxDifference(0, 1);

        // Calculate the total stones using the prefix sums
        int totalStones = prefixSums[n];

        // Calculate Alice's stones based on the maximum difference
        int aliceStones = (totalStones + maxDifference) / 2;

        return aliceStones;
    }

    private int findMaxDifference(int i, int M) {
        if (i >= n) {
            return 0;
        }

        if (memo[i][M] != Integer.MIN_VALUE) {
            return memo[i][M];
        }

        int maxDiff = Integer.MIN_VALUE;

        for (int X = 1; X <= 2 * M && i + X <= n; X++) {
            int currentStones = prefixSums[i + X] - prefixSums[i];
            int nextDiff = findMaxDifference(i + X, Math.max(M, X));
            maxDiff = Math.max(maxDiff, currentStones - nextDiff);
        }

        memo[i][M] = maxDiff;
        return maxDiff;
    }

    public static void main(String[] args) {
        Solution game = new Solution();
        int[] piles = {2, 7, 9, 4, 4};
        System.out.println(game.stoneGameII(piles)); // Expected Output: 10
    }
}

Python

from typing import List, Optional

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        memo = [[float('-inf')] * (n + 1) for _ in range(n)]
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + piles[i]

        def find_max_difference(i: int, M: int) -> int:
            if i >= n:
                return 0
            if memo[i][M] != float('-inf'):
                return memo[i][M]
            max_diff = float('-inf')
            for X in range(1, min(2*M, n - i) + 1):
                current = prefix[i+X] - prefix[i]
                next_diff = find_max_difference(i+X, max(M, X))
                max_diff = max(max_diff, current - next_diff)
            memo[i][M] = max_diff
            return max_diff

        max_difference = find_max_difference(0, 1)
        total = prefix[n]
        alice = (total + max_difference) // 2
        return alice

Complexity

• Time: O(n^2), , where n is the number of piles.
  • There are O(n²) unique states for (i, M):
    • i ranges from 0 to n-1 (start index of remaining piles).
    • M ranges from 1 to n (maximum value for M is n).
  • For each state, the inner loop runs at most O(n) times (since X can go up to 2M, but M ≤ n).
  • However, due to memoization, each state is computed only once, so the total number of recursive calls is O(n²).
  • Thus, the overall time complexity is O(n²).
• Space: O(n^2)
  • The memoization table memo is of size n × (n+1): O(n²).
  • The prefix sum array is O(n).
  • The recursion stack can go up to O(n) in depth.