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

# 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(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[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[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 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  Valid Perfect Square Leetcode Solution

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 