Home » Technical Interview Questions » Dynamic Programming Interview Questions » Stone Game II Leetcode

Stone Game II Leetcode


What is Stone Game II Problem?

Stone Game II LeetCode is a very famous problem on leetcode which is solved using the DP approach. The statement of the problem is described as two players A and B are playing a stone game. There are N number of piles each pile containing some stones. Player A will always start the game. A and B are supposed to pick all the stones in first X piles where  1<=X<=2M (initially M = 1)  one by one until no more piles are left. The objective is to end the game with Player A having maximum stones. Print the maximum stones that can be collected by Player A.

Stone Game II Leetcode

As the total possible stones of Player A can be 8 or 10, the output will be maximum of all possible outcomes i.e. 10.

Example

Input 

piles = [5, 3, 4, 5]

Output 

10

Input 

piles = [2, 7, 9, 4, 4]

Output 

10

Dynamic Programming Method

Algorithm

  1. Initialize a list containing piles of stones.
  2. Create an array sum of size n+1.
  3. Update the sum array with the number of stones in each pile.
  4. Create a 2D-DP array and set all values as 0.
  5.  Store the values in sum array in the last dp array.
  6. Traverse and update dp array as dp[i][j] = max(dp[i][j], sum[i] – dp[i+x][max(j,x)]).
  7. Return the maximum stones of player A.

Time Complexity: O(n3)

Space Complexity: O(n2)

C++ Program for Stone Game II Leetcode

#include<bits/stdc++.h>
using namespace std;

class Stone{
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        if(n == 0)  
            return 0;
        
        vector<int>sum(n+1, 0);
        
        for(int i=n-1; i>=0; i--){
           sum[i] = piles[i] + sum[i+1]; 
        }  
        
        vector<vector<int>>dp(n+1, vector<int>(n+1,0));
        for(int i = 0; i <= n; i++){
            dp[i][n] = sum[i];
        }    
        
        for(int i=n-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                for(int x=1; x<=2*j && i+x<=n; x++)
                    dp[i][j] = max(dp[i][j], sum[i] - dp[i+x][max(j,x)]);
            }
        }
        return dp[0][1];
    }
};

int main(){
    
    Stone s;
    vector<int> piles = {5, 3, 4, 5};
    cout<<s.stoneGameII(piles);
    
}
10

Java Program for Stone Game II Leetcode

import java.util.*;
class Stone{
    
    static int stoneGameII(int[] piles){
        int n = piles.length;
        if(n == 0)  
            return 0;
        
        int[] sum = new int[n+1];    
        int[][] dp = new int[n+2][n+2];
        
        for(int i=0; i<n; i++){
            sum[i]=0;
        }
        
        for(int i=n-1; i>=0; i--){  
            sum[i] = piles[i] + sum[i+1];
        }  
        
        for(int i = 0; i <= n; i++){
            dp[i][n] = sum[i];
        }    
        
        for(int i=n-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                for(int x=1; x<=2*j && i+x<=n; x++){
                    dp[i][j] = Math.max(dp[i][j], sum[i] - dp[i+x][Math.max(j,x)]);
                }    
            }
        }
        
        return dp[0][1];
    }
    
  public static void main (String[] args){
      
    int piles[] = {5, 3, 4, 5};
    
    System.out.println(stoneGameII(piles));
  }
}
10

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup