1140. Stone Game II LeetCode Solution

Last updated: February 22, 2025

In this guide, you will get 1140. Stone Game II LeetCode Solution with the best time and space complexity. The solution to Stone Game II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Stone Game II solution in C++
Stone Game II solution in Java
Stone Game II solution in Python
Additional Resources

1140. Stone Game II LeetCode Solution image

Problem Statement of Stone Game II

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.
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). Initially, M = 1.
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.

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 stones 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 stones in total.

So we return 10 since it’s larger.

Example 2:

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

Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 104

Complexity Analysis

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

1140. Stone Game II LeetCode Solution in C++

class Solution {
 public:
  int stoneGameII(vector<int>& piles) {
    const int n = piles.size();
    vector<vector<int>> mem(n, vector<int>(n));
    vector<int> suffix = piles;  // suffix[i] := sum(piles[i..n))
    for (int i = n - 2; i >= 0; --i)
      suffix[i] += suffix[i + 1];
    return stoneGameII(suffix, 0, 1, mem);
  }

 private:
  // Returns the maximum number of stones Alice can get from piles[i..n) with M.
  int stoneGameII(const vector<int>& suffix, int i, int M,
                  vector<vector<int>>& mem) {
    if (i + 2 * M >= mem.size())
      return suffix[i];
    if (mem[i][M] > 0)
      return mem[i][M];

    int opponent = suffix[i];

    for (int X = 1; X <= 2 * M; ++X)
      opponent = min(opponent, stoneGameII(suffix, i + X, max(M, X), mem));

    return mem[i][M] = suffix[i] - opponent;
  }
};
/* code provided by PROGIEZ */

1140. Stone Game II LeetCode Solution in Java

class Solution {
  public int stoneGameII(int[] piles) {
    final int n = piles.length;
    int[][] mem = new int[n][n];
    int[] suffix = new int[n]; // suffix[i] := sum(piles[i..n))
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, -1));
    suffix[n - 1] = piles[n - 1];
    for (int i = n - 2; i >= 0; --i)
      suffix[i] = suffix[i + 1] + piles[i];
    return stoneGameII(suffix, 0, 1, mem);
  }

  // Returns the maximum number of stones Alice can get from piles[i..n) with M.
  private int stoneGameII(int[] suffix, int i, int M, int[][] mem) {
    if (i + 2 * M >= suffix.length)
      return suffix[i];
    if (mem[i][M] != -1)
      return mem[i][M];

    int opponent = suffix[i];

    for (int X = 1; X <= 2 * M; ++X)
      opponent = Math.min(opponent, stoneGameII(suffix, i + X, Math.max(M, X), mem));

    return mem[i][M] = suffix[i] - opponent;
  }
}
// code provided by PROGIEZ

1140. Stone Game II LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents