Anish and Stacks!

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
9 upvotes
Asked in company
Microsoft

Problem statement

Anish has become very attentive in his data structures classes. Now his teacher has given the assignment to implement N stacks in a single array of length L. Since he has been very inattentive in his data structure classes, he can’t solve the problem on his own. Can you help him out?

Example:-
Let, 

N = 5
L = 10
1 1 3 [PUSH (1 ,4)]
1 1 4 [PUSH (1 ,3)] 
2 1 [POP(1)] 
2 2 2 [PUSH(2,2)] 
2 2 [POP(2)]

Answer:- [0, 0, 4, 0, 2]
 (The first stack has 4 and 3 so 4 is popped out from stack 1 and stack 2 has integer 2 in it, so 2 is popped out from stack 2) .
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains three integers ‘L’, ‘N’, and ‘Q’ denoting the number of stacks to be implemented and the number of queries to be performed.

The next ‘Q’ lines of every test case contain 3 integers ‘A’, ‘B’, and ‘C’ denoting the type of operation, the stack number on which the operation is to be achieved, and the number to be pushed if ‘A’ is 1.

The next ‘Q’ lines of every test case contain 2 integers ‘A’, and ‘B’ denoting the type of operation, and the stack number on which the operation is to be achieved if 'A' is 2.
Output Format :
For each test case, print an integer denoting the number popped out if ‘A’ is 2 if there exists a number in the stack otherwise print -1. If ‘A’ is 1, if the push operation is successful, print 0, otherwise print -1 if the stack is full.

The output of each test case should be printed in a separate line.
Note :
You are not required to print anything, it has already been taken care of. Just implement the function.    
Constraints :
1 <= T <= 5
1 <= L <= 10^5
1 <= N <= 10^5
1 <= Q <= 10^5
1 <= A <= 2
1 <= B <= N
1 <= C <= 10^9  

Time Limit: 1 sec
Sample Input 1 :
1
10 1 5
1 1 1
1 1 3
2 1
2 1
2 1
Sample Output 1 :
0
0
3
1
-1 
Explanation for Sample Output 1 :
In the first two operations, the answer should be 0 because the push operations are performed successfully. Then for the next two operations, the numbers 3 and 1 are popped out and they are printed. In the last operation, -1 is printed because the stack is already empty.
Sample Input 2 :
1
10 2 1
2 2 
Sample Output 2 :
-1
Hint

Make equal divisions and perform normal operations on them.

Approaches (2)
Divide the array into equal sizes of N.

We can divide the full array into equal sizes of N and perform push operations if the mentioned stack is not full and pop the top element if the stack is not empty.

 

Algorithm:-

 

  • Initialize an empty array named ANS to store all the answers.
  • Initialize an array name SIZE of length N with 0 to store the current size of all the stacks.
  • Initialize a variable name FULL and update it with L divided by N
  • Iterate from 0 to Q. (Let’s say the iterator be i).
    • If A is equal to 1,
      • If SIZE[B] is FULL, add -1 to the ANS.
      • Else, update ARR[B*FULL+SIZE[B]] to C,increment SIZE[B] by 1 and return 0.
    • Else,
      • If SIZE[B] is 0, add -1 to ANS.
      • Else, add ARR[B*FULL+SIZE[B]-1] to the answer and decrement SIZE[B] by 1.
  • Return ANS.
Time Complexity

O(Q), where Q is the number of queries

Each query takes constant time, so for Q queries the total time complexity is O(Q).

Space Complexity

O(Q),

We are using an auxiliary array to store the current size of all the stacks, so the space complexity is O(Q).

Code Solution
(100% EXP penalty)
Anish and Stacks!
Full screen
Console