I was solving the Game of Two Stack problem on HackerRank and I am unsure of why my recursive python algorithm is failing some of the test cases.
https://www.hackerrank.com/challenges/game-of-two-stacks
My code is
def twoStacks(maxSum, a, b):
# Write your code here
res, a_index, b_index = 0, 0, 0
return recur(res, a_index, b_index, maxSum, a, b)
def recur(res, a_i, b_i, maxSum, a, b):
if maxSum < 0:
return res-1
res += 1
if a_i < len(a) and b_i < len(b):
return max(recur(res, a_i+1, b_i, maxSum - a[a_i], a, b),recur(res, a_i, b_i+1, maxSum - b[b_i], a, b))
elif a_i < len(a):
return recur(res, a_i+1, b_i, maxSum - a[a_i], a, b)
elif b_i < len(b):
return recur(res, a_i, b_i+1, maxSum - b[b_i], a, b)
return res-1
My intention is to increment pointers (a_index and b_index) to simulate the popping of the top element from the stack. The recursive function will terminate when maxSum is less than 0. While the pointers are less than the length of their respective stacks, I will check the possibility of popping from either stack A or B.
I am failing test case 8-13 due to runtime error and test case 2-3 due to timeout. I understand there are other algorithms to solve this problem, but would like to understand why my recursive answer is incorrect.
