Implement A PlatesStack

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
AmazonAdobeFacebook

Problem statement

You are given an infinite number of stacks which are arranged in a row. All the stacks have the same maximum capacity.

You are supposed to implement the PlatesStack class that can perform the following operations efficiently:

PlatesStack(int N) - Constructor to initialize the object where N denotes the maximum capacity of each stack.

push(int value) - This function inserts the integer "value" in the leftmost stack which is not filled up to the maximum capacity.  

pop() - This function returns the value at the top of the rightmost stack which is not empty and removes it from that stack or returns -1 if all the stacks are empty.

popAtStack(int index) - This function returns the value at the top of the stack with the given index and removes it from that stack and returns -1 if that stack is empty.

You have to answer multiple queries, each query will correspond to one of the above-mentioned operations.

TYPE 1 corresponds to the push operation.
TYPE 2 corresponds to the pop operation.
TYPE 3 corresponds to the popAtStack operation.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer T denoting the number of test cases. The test cases follow.

The first line of each test case contains an integer N denoting the maximum capacity of the stacks.

The second line of each test case contains an integer Q denoting the number of queries to be answered.

The next Q lines contain two integers TYPE and X separated by a single space. The integer TYPE denotes the type of the query and X denotes the value or the index of the stack on which the operation is to be performed.
For TYPE-2 query, value of X is always -1. You can ignore this integer.
Output Format : 
For each query of type 2 print the value at the top of the rightmost stack or print -1 if all the stacks are empty.
For each query of type 3 print the value at the top of the stack with the given index or print -1 if the stack at the given index is empty. 

Print the answer for query in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given class.
Constraints : 
1 <= T <= 5
1 <= N <= 10
1 <= Q <= 1000
1 <= TYPE <= 3
1 <= value <= 10^9

Where "value" is the integer to be inserted into the stack or the index of the stack depending on the type of the query.

Time Limit: 1 sec
Sample Input 1 :
2
2
11
1 5
1 4
2 -1
1 3
3 1
1 2
3 2
3 3
2 -1
2 -1
2 -1
1
3
1 1
3 2
2 -1
Sample Output 1 :
4
3
-1
-1
2
5
-1
1
Explanation For Sample Input 1 :
For the first test case,
Query 1: 5 is inserted in stack-1
Query 2: 4 is inserted in stack-1
Query 3: 4 get popped out of stack-1
Query 4: 3 is inserted in stack-1
Query 5: 3 get popped out of stack-1
Query 6: 2 is inserted in stack-1
Query 7: Stack - 2 is empty so, -1
Query 8: Stack - 3 is empty so, -1
Query 9: 2 get popped out of stack-1
Query 10: 5 get popped out of stack-1
Query 11: All stacks are empty, so -1.

For the second test case,
Query 1: 1 is inserted in stack - 1
Query 2: Stack - 2 is empty so, -1
Query 3: 1 get popped out of stack - 1
Sample Input 2 :
2
2
8
1 1
2 -1
1 1
1 2
1 3
2 -1
2 -1
3 1
1
1
3 5
Sample Output 2 :
1
3
2
1
-1
Hint

Can you think of some data structure to keep track of different stacks?

Approaches (1)
Two Pointers and Hashing approach

The idea is to maintain pointers to keep track of where to push or to pop an element. And whenever push or pop is called, update the pointers accordingly. For keeping track of stack pointers let’s define a HashMap in which the key will be an integer and the value will be a stack of integers.

 

The algorithm is as follows -

 

  • Maintain two-pointers current and last to keep track of the leftmost stack push and the rightmost stack pop operations.
  • Declare the count variable to store the number of elements.
  • The push(value) function can be implemented as follows :
    • Keep incrementing the current pointer, if the stack corresponding to the current pointer has a size equal to the maximum capacity.
    • Now, the stack corresponding to the current pointer has a size less than the maximum capacity.
    • Now push the value to the stack, corresponding to the current pointer.
    • Since the last pointer should be the rightmost, update the last pointer with last = max(last, current).
    • Increment the count variable by 1.
  • The pop() function can be implemented as follows :
    1. If the count is 0, then all the stacks are empty, so return -1.
    2. Keep decrementing the last pointer, if the stack corresponding to the last pointer is empty.
    3. Save the top element of the stack, corresponding to the last pointer, and pop it.
    4. Decrement the count variable by 1.
    5. Since the current pointer should be the leftmost, update the current pointer with current = min(current, last).
    6. Return the top element.
  • The popAtStack(index) function can be implemented as follows :
    1. Return -1, If the index is not present in the map or stack corresponding to that index is empty.
    2. Save the top element of the stack, corresponding to the index pointer, and pop it.
    3. Decrement the count variable by 1.
    4. Since the current pointer should be the leftmost, update the current pointer with current = min(current, index).
    5. Return the top element.
Time Complexity

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

 

Here, since we are using hashing, all the push(), pop(), popAtStack() operations are done in constant time. Hence, the overall time complexity is O(Q).

Space Complexity

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

 

In the worst case, all the queries can correspond to the push operation in that case the total number of elements in all the stacks will be Q. Hence, the overall space complexity is O(Q).

Code Solution
(100% EXP penalty)
Implement A PlatesStack
Full screen
Console