Game of Two Stacks Solution

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

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.

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’)

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

Discard next element (‘5’) from stack 1

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

Discard next element (‘1’) from stack 1

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

Discard next element (‘2’) from stack 1

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 ;