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.

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