Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 20 Feb, 2021

Three in one

Moderate
Asked in companies
GoogleAppleFacebook

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.
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

01 Approach

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’.