Home » Technical Interview Questions » Array Interview Questions » Stone Game LeetCode

Stone Game LeetCode


Reading Time - 3 mins

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.

Stone Game

 

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
READ  Subarray Sum Equals k

Time Complexity: O(n2)

Space Complexity: O(n2)

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.

READ  Maximum Product Subarray

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions