Good solution. Can you explain how did you come up with this solution? Thanks.

awesome logic

I understand your logic, but this is not a stack operation. The only thing you can do is push and pop. You are accessing the 1st stack elements by index in the array.

Correct thing to do is push all the poped elements from first stack into a 3rd stack and pop back again while you traverse through second one.

but where is the use of stack or atleast its concept

good logic my brute force solution recursive is showing timeout for almost half of cases

are u not facing timeout problem in some of the test cases?

Implemented the same way on java. P.S.: With Scanner(System.in) the last test fails with TLE. Use Fast I/O to resolve this.

Nice approach. if we try greedy then there is problem in case where both corrosponding stack have same elements. Actually if we have problem in traversing both the stack simultaneously the best approach is to first traverse the 1st stack then start traversing second stack and manupulate the last added element from 1st stack as required in question.

It gives correct answer but wrong numbers are added to the sum in following test case:

1

3 3 4

1 1 1

99 2 0

One thing is clear from other comments here, the greedy solution will NOT work.

None of the explanations in the comment section are good at explaining how/why the given c++ solution by vkreddy21 works. I have tried explaining it below .....

So far only 1 thing is clear in the solution: When elements from 2nd stack are added, and (more recently added/last) elements from 1st stack are popped off, the solution ensures that the max count does not decrease and sum <= x (given in input).

Graphically:

A much better way to understand this is to think about what the final solution to the problem will look like.

For example, a possible solution could look like:

---

[s1 s2 s1 s2 s2 ]

where s1, s2 refer to some element from stack 1 and 2 respectively. It may be noted that all s1 elements are contiguous (since problem requires us to only pick from top of stack). Same for s2 elements.

Now, since these elements are summed (which should be <= x), this means *they can be arranged in any order. So you could group all s1 accesses and then s2 accesses * (could have also done vice-versa). this is obviously correct because for "+" operator (using which sum is being calculated) does not care about order of operands.

Hence, our previous solution can be re-arranged to look like any of the following:

---

[s2 s2 s2 s1 s1 ]

(OR)

---

[s1 s1 s2 s2 s2]

What the second case ^ suggests is that you can create a solution like:

---

[s1 s1 s1 s1 s1]

and then add (or replace s1 elements if sum is exceeding "x") s2 elements one by one, eventually leading to

---

[s1 s1 s2 s2 s2] = [s1 s2 s1 s2 s2 ]

Note that ^ this final solution is same as the ^ solution (simply created as an example for this explanation) in the earlier part of this explanation.

can someone please tell the meaning of the last if condition?

**I used same logic but few test cases did not pass: here is my correction in python 3 : **

*def twoStacks(x, a, b):

s=0
i=j=count=0
while len(a)>0 and i<len(a) and (s+a[i])<=x:
    s+=a[i]
    i+=1
count=i
while j<len(b) and i>=0:
    s+=b[j]
    j+=1
    while s>x and i>=0:
        i-=1
        s-=a[i]
    if s<=x and i+j >= count:
        count=i+j
return count*

1

5 4 8

2 1 1 1 1 10

7 8 9

For the above case, your program gives 6. But the correct answer is 5.

Above is the best solution, with O(n + m) time and O(1) space.

I tried do BFS. First attempt, passed the simple cases, but failed majority of cases.

Second attempt, I added a visted memo check using set where the memo was code snip below. Where I count the As and Bs in the search did a bit shift on Acount | with Bcount.. and this did passed more tests than first try, but still failed to pass 100% of the cases.

The set<> memo check made my BFS solution O(n+m*log(dc)) where (dc) is the distinct counts of As and Bs that are possible in the BFS. As the count score increases, (dc) gets larger and it's log(dc) because sets<> are binary search trees in c++.

Not fast enough to pass all the cases... go with the above solution.

// Path string = "ABABBBAABB..." which gets acumulated as
// BFS spans
unsigned long long path_to_long(string  const & pathstr) {
  unsigned long long acount = 0;
    unsigned long long bcount = 0;
    for(int i=0; i<pathstr.length();i++) {
        switch (pathstr[i]) {
            case 'A':
              acount++;
              break;
            case 'B':
              bcount++;
              break;
            default:
              break;
        }
    }
    return ((acount << 32)|bcount);
}	

Seriously it was helpful..I was popping the smaller element from the two stacks ...And getting wrong answers.. Thanks a ton for the cool logic

Here is my js solution, but it's not passing the whole testcases because of timeout, help me to figure out.

function twoStacks(x, a, b) {
    /*
     * Write your code here.
     */
    // console.log(x,a[0],b[0])   
    var count = 0
    var getsum = 0
    var terminate = 0
    while(getsum <= x){
        // console.log(getsum)
        if(a[0] <= b[0]){  
            var check = getsum + a[0]    
            if(check <= x){
                a.shift()
                getsum = getsum + a[0]
                count++
            }else if(check > x){
                terminate++
                if(terminate > 1){
                    break
                }
            }
            
        }else if(b[0] <= a[0]){
            var check1 = getsum + b[0]
            if(check1 <= x){
                b.shift()
                getsum = getsum + b[0]
                count++
            }else if(check1 > x){
                terminate++
                if(terminate > 1){
                    break
                }
            }
        } 
        
    }
   return count

}

i have a doubt... in the while loop where you are adding b[j] to the sum you are probably deleting more that one element in the nested while loop below it, whic makes the number of integers less for the same value of sum.****

with the same approach, using C, Im getting a TLE for TestCase 8

hello there, i was wondering... can this problem can be seen as kind of greedy for selecting maximum number of integers, as the given number can be seen as capacity and you have to select minimum of two stack tops inorder to add to the current sum, lesser current sum means more integers can be selected. if current sum exceeds capacity number of integers selected is the answer.

hey, why can't we do in a greedy way. Like taking min(stack1.top(), stack2.top()) and adding to the sum. with greedy i won't get correct answer i have tried. can you please explain the second while loop and while greedy will not work.... thank you..

I'm getting runtime error for testcase 5 while using this logic in C, can you explain why?

doubt. in the outer while loop, negative value of i will not come right?

nice solution !!!

nice one man...how you think soo deep I can't even think around your solution...

your approach is really good .

very nice

Fabulous! How did you get it?

Amazing logic man!! Hat's off!

for anyone wondering its actually the bottom element of first stack being subtracted since 'i' is at the bottom element in the beginning and is reducing every time by one.

I uesed Linked List to solve this problem

import sys

class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
        
class Stack:
    def __init__(self):
        self.top = None
    
    def isempty(self):
        if self.top is None:
            return True
        return False
    
    def peek(self):
        if not self.isempty():
            return self.top.data
        return 0
    
    def push(self, data):
        node = Node(data)
        if self.isempty():
            self.top = node
            return
        node.next = self.top
        self.top = node
        
    def pop(self):
        if self.isempty():
            raise Exception("Stack Overflow")
        data = self.top.data
        self.top = self.top.next
        return data

if __name__ == '__main__': 
    g = int(input())

    for g_itr in range(g):
        nmx = input().split()

        n = int(nmx[0])

        m = int(nmx[1])

        x = int(nmx[2])

        ni = sys.stdin.readline().strip().split()
        mi = sys.stdin.readline().strip().split()
        stack1, stack2 = Stack(), Stack()
        for i in range(n-1, -1, -1):
            stack1.push(int(ni[i]))

        for i in range(m-1,-1,-1):
            stack2.push(int(mi[i]))

        live_sum, i, j = 0, 0, 0
        junk = Stack()
        while not stack1.isempty() and live_sum + stack1.peek() <= x:
            live_sum += stack1.peek()
            junk.push(stack1.pop())
            i += 1
        count = i
        while not stack2.isempty():
            live_sum += stack2.pop()
            j += 1
            while live_sum>x and not junk.isempty():
                i-=1
                live_sum -= junk.pop()
            if live_sum<=x and i+j>count:
                count = i+j

        result = count
        print(result)

i cant understand and its not work properly

amazing!!

and this is O(n) ritght?

According to the question the program should terminate, player is disqualified if the sum is greater than max sum. And the question confuses saying its stack, which means I can't move the pointer to previous element once its read.

This algorithm works because it outputs count right, though violates sum:

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

• In the while loop i--, sum -= a(i), after i reached 0, the algorithm should do the same loop with j (stack B) because sum still > maxSum. (For example testcase 0: https://ibb.co/vjxWpwT)
• The next if statement, the condition shouldn't contain i + j > count because it means count only keeps the highest record --> This is why the algorithm outputs right.

Sum up: https://ibb.co/v1RxQk7

With this modification, the algorithm will be exactly the author beginning idea. But it leads to infinite loops.

So the "hacking" part is violates sum condition.

can you tell time complexity of this algorithm

What's the logic of decrementing i in the inner loop first and then subtracting that index, instead we can subtract that index from the sum and then decrement the index. Although your solution is working but, I didn't get that part.