I was solving problem for game of two stacks on Hackers rank and got stuck. Problem is my solution is not working when stack count is very huge (millions of entries)

https://www.hackerrank.com/challenges/game-of-two-stacks

Alexa has two stacks of non-negative integers, stack A and stack B where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:

In each move, Nick can remove one integer from the top of either stack A or B stack.

Nick keeps a running sum of the integers he removes from the two stacks.

Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer X given at the beginning of the game.

Nick's final score is the total number of integers he has removed from the two stacks.

find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified) during each game and print it on a new line.

For each of the games, print an integer on a new line denoting the maximum possible score Nick can achieve without being disqualified.

Sample Input 0

```
1 -> Number of games
10 -> sum should not exceed 10
4 2 4 6 1 -> Stack A
2 1 8 5 -> Stack B
```

Sample Output

```
4
```

Below is my solution

```
def twoStacks(x, a, b):
a_list = []
sum_list = 0
for i in range(len(a)):
sum_list = sum_list + a[i]
if sum_list <= x:
a_list.append(a[i])
else:
break
print(a_list)
print(a[i])
print(sum_list)
max_first = len(a_list)
replacement_list = []
list_a_length = len(a_list)
list_replacement_length = len(replacement_list)
list_b_length = len(b)
replacement_list_sum = 0
a_list_sum = sum(a_list)
while True:
max_first = max(max_first, list_a_length + list_replacement_length)
#print("max final is ",max_first)
#print(sum(replacement_list))
#print(sum(a_list))
#print(b[0])
#print(type(replacement_list), type(a_list), type(b))
#print("sum of a lis is", sum(a_list))
if list_b_length == 0:
break
elif replacement_list_sum + a_list_sum + b[0] <= x:
#print(b[0])
replacement_list_sum = replacement_list_sum + b[0]
replacement_list.append(b.pop(0))
list_replacement_length += 1
list_b_length -= 1
if replacement_list_sum > x:
break
elif a_list:
a_list_sum = a_list_sum - a_list[-1]
a_list.pop()
list_a_length -= 1
#print(a_list)
else:
break
# print(replacement_list)
# print(a_list)
return max_first
```

Where a is the first stack , b is second stack and x is sum in range of (1000000000)

Problem is my code is giving correct results but for large number it takes ages to give the output. any better solution is appreciated

Edit:

I changed my code and still taking ages

Initial observations:

a) The order Nick picks the solution does not matter.If S = { a1, b1,a2,b2,... } you can reorder this and pick everyone from A first, then pick B.

b) If you have a solution S = S_A + S_B , consisting of S_A elements of A and S_B elements of B. You can rephrase the solution as "Some elements S_A of A" + " as many elements as possible from B given S_A ".

Suggested pseudo code:

1) Iterate through stack A. Keep the cumulative sum.

2) For each step through A, check how many elements you can pick from B.

Optimization if necessary: You can create all cumulative sums from B, and for each partial solution from A do a binary search on this sum table to quickly determine how many elements you can grab from B.

Here is an implementaion of the suggested idea, it solves the hackerrank problem, so its kinda cheating for you if you use it :-) :