Solution of working with two stacks

queue using two stacks hackerrank solution
game of two stacks geeksforgeeks
stack using queue
merge two stacks c++
double stack in data structure
if 2 stacks are implemented using a single array of size n
stack and queue in data structure
implement queue using stack algorithm

I am trying the problem of equal stacks from Hackerrank : https://www.hackerrank.com/challenges/equal-stacks/problem.

Can someone please help me understand the difference in the logic of below two codes. While the first one fails the other one succeeds:

First(My solution):

n1, n2, n3 = map(int, input().split())
H1 = list(map(int, input().split()))
H2 = list(map(int, input().split()))
H3 = list(map(int, input().split()))

sum_h1 = sum(H1)
sum_h2 = sum(H2)
sum_h3 = sum(H3)
#print (sum_h1,sum_h2,sum_h3)

while not (sum_h1 == sum_h2 and sum_h2 == sum_h3):
    if sum_h1 > sum_h2 or sum_h1 > sum_h3:
        #t = H1.pop()
        sum_h1 -= H1[0]
        #print ("Checking:",sum_h1)
    if sum_h2 > sum_h1 or sum_h2 > sum_h3:
        #t = H2.pop()
        sum_h2 -= H2[0]
    if sum_h3 > sum_h1 or sum_h3 > sum_h2:
        #t = H3.pop()
        sum_h3 -= H3[0]
print (sum_h1)

Second solution(correct):

n1, n2, n3 = map(int, input().split())
H1 = list(map(int, input().split()))[::-1]
H2 = list(map(int, input().split()))[::-1]
H3 = list(map(int, input().split()))[::-1]

sum_h1 = sum(H1)
sum_h2 = sum(H2)
sum_h3 = sum(H3)
#print (sum_h1,sum_h2,sum_h3)

while not (sum_h1 == sum_h2 and sum_h2 == sum_h3):
    if sum_h1 > sum_h2 or sum_h1 > sum_h3:
        t = H1.pop()
        sum_h1 -= t
    if sum_h2 > sum_h1 or sum_h2 > sum_h3:
        t = H2.pop()
        sum_h2 -= t
    if sum_h3 > sum_h1 or sum_h3 > sum_h2:
        t = H3.pop()
        sum_h3 -= t
print (sum_h1)

I know in the second one we are reversing the input array . But should that make any difference.

I am completely puzzled.

Please help me in pointing out what is the issue with the first code.

Thanks in advance.

Order matters

I know in the second one we are reversing the input array . But should that make any difference.

Yes that makes a difference. Say you have the following stacks:

1
1  2  1
1  1  3

Now we can simply pop the 1 (in boldface) from the right stack, and all stacks have the same height.

But the opposite is not true. If the stacks are reversed:

1
1  1  3
1  2  1

We have to pop the right stack, since it is the largest one. But we can only pop 3 (in boldface) from it. As a result the maximum height can only be 1. When we pop the 3, we will later discover, that the maximum equal height we can obtain is 0. If we pop the right stack we obtain:

1
1  1
1  2  1

But the stack in the middle has a 2 at the bottom. So we can never produce a 1 as sum of the stack in the middle.

A stack implies an order: we have to remove the elements above a cylinder, before we can pop that element, so the order matters.

Why the first does not work.

In the first code fragment, you subtract the first element from the sum of that stack. But you do not delete that element from the list. As a result, you keep popping the first element from the stack.

You can fix it by pop(0) (popping from the beginning of the list), or deleting that element later:

# fix of the first code fragment

while not (sum_h1 == sum_h2 and sum_h2 == sum_h3):
    if sum_h1 > sum_h2 or sum_h1 > sum_h3:
        sum_h1 -= H1.pop(0)
        #print ("Checking:",sum_h1)
    if sum_h2 > sum_h1 or sum_h2 > sum_h3:
        sum_h2 -= H2.pop(0)
    if sum_h3 > sum_h1 or sum_h3 > sum_h2:
        sum_h3 -= H3.pop(0)

Or:

# fix of the first code fragment

while not (sum_h1 == sum_h2 and sum_h2 == sum_h3):
    if sum_h1 > sum_h2 or sum_h1 > sum_h3:
        sum_h1 -= H1[0]
        del H1[0]
        #print ("Checking:",sum_h1)
    if sum_h2 > sum_h1 or sum_h2 > sum_h3:
        sum_h2 -= H2[0]
        del H2[0]
    if sum_h3 > sum_h1 or sum_h3 > sum_h2:
        sum_h3 -= H3[0]
        del H3[0]

But mind that these are inefficient: popping from the start is a O(n) operation with n the size of the list.

Queue using Stacks, A queue can be implemented using two stacks. Please solve it on “PRACTICE” first, before moving on to the solution. two stacks with costly enQueue(). A simple way to implement two stacks is to divide the array in two halves and assign the half half space to two stacks, i.e., use arr to arr[n/2] for stack1, and arr[(n/2) + 1] to arr[n-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.

Since @Willem Van Onsem and @coldspeed explained how the first solution is different from the other I thought I could explain a similar solution that could be easier to understand (in my opinion).

Let's say the stacks are as in the original problem:

3 2 1 1 1  (stack1)
4 3 2      (stack2)
1 1 4 1    (stack3)

Here, the left most number is a top of each stack and the right most is the bottom. I pick the first stack as a reference stack (but it can be any of the three). Its possible heights when removing cylinders are 8, 5, 3, 2, 1, 0. The task is to try out all the heights and see if they could be common ones. Then, the maximum common height is the answer.

Let's solve the problem from bottom to top. So, the stacks are empty and we want to build them from the beginning. While building them we'll find all the stack configurations for which their heights are equal. So, the configuration with the maximum height will be an answer to the question.

  1. Initially maximum common height as well as current heights for each stack are 0

    0
    0
    0
    0 (max)
    
  2. Add 1 to stack1's height. Then, because the current height of stack2 is less than that of stack1 keep increasing it by summing the bottom elements. Do the same for stack3

    1
    2
    1
    0 (max)
    

    Since the heights are different max remains 0. So, 1 can't be a common height for the stacks.

  3. Add 1 to stack1's height. stack2's height is equal so do nothing for it. For stack3 keep summing up as long as the height is less.

    2
    2
    5
    0 (max)
    
  4. 3
    5
    5
    0 (max)
    
  5. 3
    5
    5
    0 (max)
    
  6. 5
    5
    5
    5 (max)
    
  7. 8
    9
    10
    5 (max)
    
  8. Output the max height as the first stack is empty and it doesn't make sense to work with other stacks (if they're still non-empty).

    5 (max)
    

Now, the algorithm itself (in Python3 for simplicity):

n, m, k = map(int, input().split())
stack1 = list(map(int, input().split()))
stack2 = list(map(int, input().split()))
stack3 = list(map(int, input().split()))

max_height = 0
height1 = 0
height2 = 0
height3 = 0

while len(stack1) > 0:
    if len(stack1) > 0:    
        height1 += stack1.pop() 
    while len(stack2) > 0 and height2 < height1:
        height2 += stack2.pop()        
    while len(stack3) > 0 and height3 < height1:
        height3 += stack3.pop()  

    if height1 == height2 == height3:
        max_height = height1     

print (max_height)  

Implement two stacks in an array, Create a data structure twoStacks that represents two stacks. Recommended: Please solve it on “PRACTICE” first, before moving on to the solution. A simple way to implement two stacks is to divide the array in two halves and assign the  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).

The difference between your solution and the correct one is that your stacks are reversed. In this case, you should be calling list.pop(0) to remove the first element.

while not (sum_h1 == sum_h2 and sum_h2 == sum_h3):
    if sum_h1 > sum_h2 or sum_h1 > sum_h3:
        t = H1.pop(0) # -------------- pop 0th element 
        sum_h1 -= t  
    if sum_h2 > sum_h1 or sum_h2 > sum_h3:
        t = H2.pop(0)  # -------------- pop 0th element 
        sum_h2 -= t
    if sum_h3 > sum_h1 or sum_h3 > sum_h2:
        t = H3.pop(0)  # -------------- pop 0th element 
        sum_h3 -= t
print (sum_h1)

For this input:

5 3 4
3 2 1 1 1
4 3 2
1 1 4 1

This is the output:

5

Game of Two Stacks Discussions | Data Structures, Find the maximum number of integers Nick can remove from the stacks One thing is clear from other comments here, the greedy solution will NOT work. The trick is the queue is virtual and there only needs to be 1 copy of each number across the two stacks so if the pop/top stack has 5,4,3 then the push stack would be empty. New items go on the stack that is the back of the line while they come off the stack that is the front of the line 6 |

queue-using-two-stacks hackerrank Solution, QUEUE-USING-TWO-STACKS hackerrank Solution - Correct, Optimal and Working. /* * Author: Arpit Bhayani * https://arpitbhayani.me */ #include <cmath>  Following are the steps to print postorder traversal of the above tree using two stacks. 1. Push 1 to first stack. First stack: 1 Second stack: Empty 2. Pop 1 from first stack and push it to second stack. Push left and right children of 1 to first stack First stack: 2, 3 Second stack: 1 3.

HackerRank-Solutions/Queues, GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together. Sign up. Branch: master. Given a stack of integers, sort it in ascending order using another temporary stack. We follow this algorithm. Create a temporary stack say tmpStack. Here is a dry run of above pseudo code. // a auxiliary stack. # stack using auxiliary stack. # Function to create a stack. // a auxiliary stack. This article is contributed by Aditya Nihal Kumar

HackerRank-Solutions-in-Python/Queues: A Tale of Two Stacks at , GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together. Sign up. Branch: master. We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them. A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Comments
  • Your logic is right, except in OP's solution he's indexing H[0], so he's still subtracting 1. I don't think the order is the issue. OP isn't calling H.pop(0).
  • @Coldspeed: but pop() pops from the right of the list (so the top of the stack). That's why the first fails whereas the second succeeds.
  • pop(0) pops from the start. And in OP's case with the stacks reversed, pop(0) is the right operation, which OP isn't doing (from what I see). >>> x = [1, 2, 3]; >>> x.pop(0); 1
  • @Coldspeed: I did not notice the lists were not reversed in the first code fragment. Fixed.