Stone Game II

Leetcode Daily Challenge (26th May, 2023)

26 May, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/stone-game-ii/description/

Problem Explanation with 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

Constraints

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

Intuition:-

We can simulate a game here and in alice's turn we will try to maximize the score and in bob's turn we will try to minimize the score.
Carry 3 parameters: the number of piles allowed to take, the current index and the current player.
Return the maximum score alice can get.

Solution:-

Create a recursive function solve(m,i,ch) where m is the number of piles allowed to take, i is the current index and ch is the current player.
If the current index is greater than or equal to the length of the piles, return 0. (base case)
Initialize ans = 0 if ch == 0 which means it is alice's turn else initialize ans = inf which means it is bob's turn.
Initialize tot = 0 which will store the sum of the piles till each index.
Iterate over piles from 1 to 2*m+1 and if the current index + X is greater than the length of the piles, break.
Add the current pile to tot.
If ch == 0, it is alice's turn so update ans = max(ans,tot+solve(max(m,X),i+X,1)) else it is bob's turn so update ans = min(ans,solve(max(m,X),i+X,0)).
Return and.
Return solve(1,0,0) which means initially alice can take 1*2 pile, the current index is 0 and it is alice's turn.

Code:-

JAVA Solution

class Solution {
    public int stoneGameII(int[] piles) {
        int[][] memo = new int[piles.length][piles.length];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(1, 0, 0, piles, memo);
    }

    private int solve(int m, int i, int ch, int[] piles, int[][] memo) {
        if (i >= piles.length) {
            return 0;
        }
        if (memo[i][m] != -1) {
            return memo[i][m];
        }
        int ans = 0;
        int tot = 0;
        for (int X = 1; X <= 2 * m; X++) {
            if (i + X > piles.length) {
                break;
            }
            tot += piles[i + X - 1];

            if (ch == 0) {
                ans = Math.max(ans, tot + solve(Math.max(m, X), i + X, 1, piles, memo));
            } else {
                ans = Math.min(ans, solve(Math.max(m, X), i + X, 0, piles, memo));
            }
        }
        memo[i][m] = ans;
        return ans;
    }
}

Python Solution

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @cache
        def solve(m,i,ch):
            if i >= len(piles):
                return 0
            ans = 0 if ch==0 else float('inf')
            tot = 0
            for X in range(1,2*m+1):
                if i + X > len(piles):
                    break
                tot += piles[i+X-1]

                if ch == 0:
                    ans = max(ans,tot+solve(max(m,X),i+X,1))
                else:
                    ans = min(ans,solve(max(m,X),i+X,0))
            return ans

        return solve(1,0,0)

Complexity Analysis:-

TIME:-

The time complexity of add method is O(n^3) because of the nested loops and recursive calls.

SPACE:-

The space complexity is O(n^2) due to the memoization array memo with dimensions piles.length by piles.length.

References:-

Connect with me:-

java

python

leetcode

dsa