Quick Links

## Problem Statement of Game of Two Stacks

You are given two stacks **S1 **and **S2**. You have to pic numbers from stack by deleting top element and add them in the resultant sum. The element deleted must be added into the sum. The sum must not exceed the given value of **K**. Number of elements picked is called score. You have to maximize the score. The original problem statement of Game of Two Stacks challenge is available on Hackerrank.

## Basic Greedy Approach for Game of Two Stacks

As the number of elements selected in the resultant set is to be maximized without exceeding **K**, the Greedy approach can be applied.

### Greedy Criteria

Compare the top elements of both stacks and select the smaller one if the total sum does not exceed **K**. In this way we can select maximum number of elements within the limit of **K**. Consider the following example, where two stack **S1** and **S2** are given and **K=15**.

### Processing of Greedy Approach

Initially **SUM = 0**

**SUM = SUM + 2 = 2**

**SUM = SUM + 1 = 3**

**SUM = SUM + 3 = 6**

**SUM = SUM + 1 = 7**

**SUM = SUM + 2 = 9**

**SUM = SUM + 2 = 11**

**SUM = SUM + 3 = 14**

Now** 5** and **7 **are compared and** 5 **should be selected as it is smaller but by considering **5** the **SUM** will become **19** which is greater than **K (=15)**. So neither of **5** or **7** can be selected. So We could select** 2 **elements from **stack 1** and **5** elements from **stack 2**. Our score is **7**, which is best.

### Pseudo Code for Greedy Solution of Game of Two Stacks

```
S1 []; // stack 1, n elements stored from 1 to n
S2 []; // stack 2, m elements stored from 1 to m
K;
count = 0; // Too count number of elements selected
SUM = 0;
PSUM = 0
i = n; // Top of S1
j = m; // Top of S2
While (i > 0 && j >0)
{
if(S1[ i ] < = S2[ j ]) {
PSUM = PSUM + S1[ i ];
i--;
}
else {
PSUM = PSUM + S1[ j ];
j--;
}
if( PSUM <= K) {
SUM = PSUM;
count ++;
}
else
break;
}
Print : count;
```

### Analysis of Greedy Approach

The size of **stack 1** is **n **and **stack 2** is **m**. The above approach goes like merge operation for two arrays and hence the time complexity is **O(n + m)**.

## O(n) Solution of Game of Two Stacks

The running time can be reduced if reduce the number of comparisons. In above solution we are comparing every element of **stack 1** to every element of **stack 2**. But now we will change the strategy, as follows:

### Step 1 – Take Elements from stack 1

First we will take maximum possible elements from stack 1 without the sum exceeding K.

From **stack 1** elements **2,1,5** and **6** are selected.**current_SUM = 2+1+5+6 = 14 (<K)****Best_Score = 4 **(**4** elements selected)**space_AVAIL = K – current_SUM = 15 – 14 = 1 **

### Step 2 – Include elements from stack 2

Now, we will try to select as many elements as possible from **stack 2** in the ** space_AVAIL**. To try all the possibilities, we will discard elements from **stack 1 **which are already selected one by one to create room for elements from **stack 2** and try to find better solution (maximize **Best_Score**). **space_AVAIL** is **1** and **3** is on top of stack** 2** so it can not be selected.

#### Discard Last selected item from stack 1 (‘6’)

**current_SUM = 2+1+5 = 8****space_AVAIL = K – current_SUM = 15 – 8 = 7****current_Score = 3** (as one element is discarded)

#### Select items from stack 2 (3, 1 and 2) in the space created

**current_SUM = 2+1+5+3+1+2 = 14****space_AVAIL = K – current_SUM = 15 – 14 = 1****current_Score = 6 **(**3** new elements included) **Best_Score = current_Score = 6 **(because **current_Score > Best_Score**)

#### Discard next element (‘5’) from stack 1

**current_SUM = 2+1+3+1+2 = 9****space_AVAIL = K – current_SUM = 15 – 9 = 6 ****current_Score = 5** (**1** element excluded)

#### Select items from stack 2 (2 and 3) in the space created

**current_SUM = 2+1+3+1+2 +2 + 3 = 14space_AVAIL = K – current_SUM = 15 – 14 = 1current_Score = 7** (

**2**new elements included)

**Best_Score = current_Score = 7**(because

**current_Score > Best_Score**)

#### Discard next element (‘1’) from stack 1

**current_SUM = 2+3+1+2 +2 + 3 = 13space_AVAIL = K – current_SUM = 15 – 13 = 2current_Score = 6** (

**1**element excluded)

We can not select any element from stack **2 **(**7 > space_AVAIL**). No improvement in **Best_Score**.

#### Discard next element (‘2’) from stack 1

**current_SUM = 3+1+2 +2 + 3 = 11space_AVAIL = K – current_SUM = 15 – 11 = 4 current_Score = 5** (

**1**element excluded)

We can not select any element from **stack 2** (**7 > space_AVAIL**). No improvement in **Best_Score**. Now, no element is there to discard from **stack 2**. Best score is **7**. So the answer is **7**.

### Pseudo Code for Game of Two Stacks

```
S1 []; // stack 1, n elements stored from 1 to n
S2 []; // stack 2, m elements stored from 1 to m
K;
current_SUM = 0;
space_AVAIL = k;
current_Score = 0;
Best_Score = 0;
p = n; // Top of S1
q = m; // Top of S2
while(p > 0 AND (current_SUM + S1[ p ] <= K)) {
current_SUM = current_SUM + S1[ p ];
current_Score = current_Score + 1;
space_AVAIL = K – current_SUM;
p = p – 1;
}
p = p + 1; \\ set on last selected item of stack 1
Best_Score = current_Score;
While(p <= n) {
temp_SUM = 0;
temp_Count = 0;
while(q > 0 AND space_AVAIL >= 0){
temp_SUM = temp_SUM + S2[q];
space_AVAIL = space_AVAIL – S2[q];
temp_Count ++;
q--;
}
if(space_AVAIL < 0 ) {
q = q + 1;
temp_SUM = temp_SUM – S2[q];
space_AVAIL = space_AVAIL + S2[q];
temp_Count -- ;
}
current_SUM = current_SUM + temp_SUM;
Best_Score = current_Score = current_Score + temp_Count;
current_SUM = current_SUM – S1[p];
p++;
space_AVAIL = K – current_SUM;
current_Score = current_Score -1;
temp_SUM = 0;
temp_Count = 0;
while(q > 0 AND space_AVAIL >= 0){
temp_SUM = temp_SUM + S2[q];
space_AVAIL = space_AVAIL – S2[q];
temp_Count ++;
q--;
}
if(space_AVAIL < 0 ) {
q = q + 1;
temp_SUM = temp_SUM – S2[q];
space_AVAIL = space_AVAIL + S2[q];
temp_Count -- ;
}
current_SUM = current_SUM + temp_SUM;
current_Score = current_Score + temp_Score;
if(current_Score > Best_Score)
Best_Score = current_Score;
}
Print : Best_Score ;
```