Three in one

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in companies
AppleFacebookCvent

Problem statement

Given a sequence of queries of insertion and deletion from 3 stacks, you need to implement three stacks using a single array such that the size of the array doesn’t exceed the number of queries.

In each query, the input is of two types :

Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack.

Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.

After each pop operation, you have to print the element which is removed.

Note: If a pop operation is used in an empty stack nothing happens to the stack, but you have to print -1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains ‘Q’ denoting the number of queries.

In the next Q lines input is either of the types :

    Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack. 

    Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.
Output Format : 
For each query of type 0, If the stack is non-empty print the removed element.

If a stack is empty print -1.

Print each element in the new line.
Constraints : 
1 <= T <= 3
0 <= Q, ele  <= 10^5
0 <= id <= 2  , denoting one of the three stack

Time Limit : 1 sec
Sample Input 1 :
1
6
0 0
0 1 5
0 1 4
1 1 9
1 0
0 0
Sample Output 1 :
-1
9
4
Explanation for Sample Input 1 :
Initially stack_0= {} , stack_1 ={} , stack_2={} , i.e. all are empty

1st query: pop  from stack 0
Since stack 0 is empty : print -1
stack_0= {} , stack_1 ={} , stack_2={}

2st query: push 5 in stack 0
stack_0= {5} , stack_1 ={} , stack_2={}

3st query: push 4 in stack 0
stack_0= {5,4} , stack_1 ={} , stack_2={}

4st query: push 9 in stack 1
stack_0= {5,4} , stack_1 ={9} , stack_2={}

5st query: pop from stack 1
Tos of stack_1 is 9 : print 9
stack_0= {5,4} , stack_1 ={)  , stack_2={}

6st query: pop from stack 0
Tos of stack_0 is 4 : print 4
stack_0= {5} , stack_1 ={} , stack_2={}

Therefore the output is: -1, 9, 4
Sample Input 2 :
1
3
0 0
1 0
2 0
Sample Output 2 :
-1
-1
-1
Hint

create a prev array that keeps tracks of the previous position of the element in the stack

Approaches (2)
Brute

You will create an array ‘arr’ of size Q which will keep all the elements pushed in three arrays. Since we are using 3 stacks in a single array, we need to have a way of finding the position of the top of the stack (tos) in the array, for which we will store the tos position of all 3 stacks. You also need an array ‘prev’ of size Q, where prev[i] tells what is the index of the prev element in the current stack.

Eg: if the input is

1

7

0 1 5

0 1 1

1 1 6

2 1 8

0 1 4

1 1 2

0 1 6

Then our arrays will be like this:

tos= {6 , 4, 3} , // tos stores position of top of stack

Prev[1] =0, because in stack 0 if we pop the element at position 1, the tos will be 5 which is at position 0.

 

Algo for pop operation:

  • If tos of the stack is -1, then it means the stack is empty, print -1.
  • If tos is not -1, then print the element at position tos, mark the current position in ‘arr’ array as -1 representing its empty and change the

tos[stack_id]= prev[ tos[ stack_id ] ].

 

Algo for push operation:

  • Find an empty index in the array, say emp_id.
  • Then change prev[ emp_id ] = tos[stack_id], to link the next element that is to be pushed.
  • Update tos as tos[ stack_id] =emp_id, and update value at position emp_id in array ‘arr’.
Time Complexity

There are Q queries and in each query, the most expensive job is finding an empty index in the array where we have pushed an element. This is done in O(Q) thus net time complexity is O(Q^2). 

Space Complexity

We are only using arrays of the size of Q, thus space complexity is O(Q)

Code Solution
(100% EXP penalty)
Three in one
Full screen
Console