Last Updated: 20 Feb, 2021
Three in one
Moderate
Asked in companies
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.
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
Approaches
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’.
The approach is mostly the same as brute force, the only difference is instead of doing findEmptyIndex() in O(Q), we will do it in O( log(Q) ) using set or priority queue.
Or we can also do it in O(1) using unordered_set