Stone Game LeetCode

What is Stone Game problem?

Stone Game LeetCode – Two players A and B are playing a stone game. There are even numbers of piles each pile containing some stones and the total stones in all the piles is odd. A and B are supposed to pick a pile either from the starting or end of the row one by one until no more piles are left. Player A will always start the game by picking a pile first. The player with more stones at the end wins the game. Print true if and only if player A wins the game else print false. This question is very common in LeetCode.

Therefore, the output will be true because A is the winner assuming he starts the game. Below is an example of a stone game leetcode.

Example

Input : piles = {5, 3, 4, 5}

Output : True

Input : piles = {5, 3, 4, 5, 3, 7}

Output : True

Dynamic Programming Method

LeetCode’s Stone Game problem can be solved using Dynamic Programming

Algorithm

1. Initialize a list containing piles of stones.
2. Create a 2D-DP array and set all values as 0.
3. Each player has two choices when remaining piles are piles[i], piles[i+1], …. piles[j] therefore chance of player can be found comparing j-i to n modulo 2.
4. Player A either chooses piles[i] or piles[j] in order to maximize its stones.
5. Player B either chooses piles[i] or piles[j] in order to minimize its stones.
6. Return true if A has more stones

Time Complexity: O(n²)

Space Complexity: O(n²)

C++ Program

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

class Stone{
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();

        int dp[n+2][n+2];
        memset(dp, 0, sizeof(dp));

        for(int size = 1; size <= n; ++size)
            for(int i = 0, j = size - 1; j < n; ++i, ++j){
                int parity = (j + i + n) % 2; 
                if(parity == 1)
                    dp[i+1][j+1] = max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]);
                else
                    dp[i+1][j+1] = min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]);
            }
        return dp[1][n] > 0;
    }
};
int main(){
    Stone s;
    vector<int> piles = {5, 3, 4, 5};
    if(s.stoneGame(piles)){
        cout<<"True";
    }
    else{
        cout<<"False";
    }
}

True

Java Program

import java.util.*;

class Stone{
    
    static boolean stoneGame(int[] piles){
        int n = piles.length;

        int[][] dp = new int[n+2][n+2];
        
        for(int size = 1; size <= n; ++size)
            for(int i = 0; i + size <= n; ++i){
                int j = i + size - 1;
                int parity = (j + i + n) % 2;
                if(parity == 1)
                    dp[i+1][j+1] = Math.max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]);
                else
                    dp[i+1][j+1] = Math.min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]);
            }

        return dp[1][n] > 0;
    }
    
  public static void main (String[] args){
      
    int piles[] = {5, 3, 4, 5};
    
    if(stoneGame(piles)){
        System.out.println("True");
    }
    else{
        System.out.println("False");
    }
  }
}

Output :
True

Mathematical Or Observed Method

Interesting facts about Stone Game LeetCode. As Player A is first to choose the stone pile and number of piles is even, this lead to an interesting fact:
Player A can always choose odd piles or always choose even piles.

Let’s say :

If Player A wants to pick piles at even positions and picks the first pile that is pile at index 0, then player B can choose either piles[1] or piles[n-1].
Every turn, Player A can always choose piles at even positions and Player B can only choose piles at odd positions.

As we know that sum of stones in piles is odd.
If the sum of piles[even] is greater than the sum of piles[odd], Player A just picks all evens and wins.
If the sum of piles[even] is less than the sum of piles[odd], Player B just picks all odds and wins.

So, Player A is always the winner in this game.

Algorithm

1. Initialize a list containing piles of stones.
2. Return True.

Time Complexity: O(1)

Space Complexity: O(1)

C++ Program

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

class Stone{
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

int main(){
    Stone s;
    vector<int> piles = {5, 3, 4, 5};
    if(s.stoneGame(piles)){
        cout<<"True";
    }
    else{
        cout<<"False";
    }
}

True

Java Program

import java.util.*;

class Stone{
    
    static boolean stoneGame(int[] piles){
        return true;
    }
    
  public static void main (String[] args){
      
    int piles[] = {5, 3, 4, 5};
    
    if(stoneGame(piles)){
        System.out.println("True");
    }
    else{
        System.out.println("False");
    }
  }
}

True

This is the famous solution of the stone game leetcode. Stone Game LeetCode question is being asked in various interviews which are based on dynamic programming.

References