Queries on Stack

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

Problem statement

You are given an empty stack and an integer ‘LIMIT’. The size of the stack cannot exceed the ‘LIMIT’.

You are given ‘Q’ queries of the following three types -:

1. PUSH ‘X’ -: Push integer ‘X’ at top of the if its size is less than ‘X’, else do nothing.

2. POP -: Pops and returns the top element of stack or -1 if the stack is empty.

3. INC ‘K’, ‘Y’-: Increments the bottom ‘K’ elements of the stack by ‘Y’. If there are fewer than X elements in the stack, just increment all the elements in the stack.

Your task is to return an array/list, that consists of all elements returned by a query of type ‘POP’ in the same order in which these queries are executed. See the example for more clarity.

Note: 
1. It is guaranteed that there is at least one query of type ‘POP’.
For Example: 
Let there be the following 10  queries and ‘LIMIT’ be 3.
[PUSH 3, PUSH 2, PUSH 1, INC 2 1, PUSH 1, POP, INC 3 3, POP, POP, POP].
Stack after 0th query, i.e PUSH 3,  be [3]
Stack after 1st query, i.e PUSH 2, be [3, 2] (top to bottom of the stack is represented by right to the left of list)
Stack after 2nd query, i.e PUSH 1, be [3, 2, 1].
Stack after 3rd query, i.e INC 2 1, be [4, 3, 1]. We increment the bottom 2 elements by 1.
Stack after 4th query, i.e PUSH 1, be [4, 3, 1] as the size of the stack cannot exceed 3.
Stack after 5th query, i.e POP, be [4, 3] and we should return 1 for this query.
Stack after 6th query, i.e INC 3 3, be [7, 6] as stack size is less than 3, so we every element.
Stack after the 7th query, i.e POP, be [7] and we should return 6 for this query.
Stack after 8th query, i.e POP, be [] and we should return 7 for this query.
Stack after the 9th query, i.e POP, be [] and we should return -1 for this query.

Thus we should return an array/list [1, 6, 7, -1].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case will contain two space-separated integers ‘Q’ and ‘LIMIT’, representing the number of queries, and maximum size of stack respectively.

The next ‘Q’ lines of each test case consist of a string that represents the type of query and then 0 to 2 space-separated integers according to types of query.
Output Format: 
For each test case, print space-separated integers returned by a query of type ‘POP’ in the same order in which these queries are executed.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 50
1 <= Q <= 10000
1 <= LIMIT <= 10000
1 <= X <= 10000
1 <= K <= 10000
1 <= Y <= 10000

Where ‘T’ is the number of test cases,  ‘Q’, ‘LIMIT’, representing the number of queries, and maximum size of stack respectively, and ‘X’, ‘K’, ‘Y’ are integers described in problem statements.

Time limit: 1 sec
Sample Input 1:
2
1 1
POP
10 3
PUSH 3 
PUSH 2 
PUSH 1
INC 2 1 
PUSH 1 
POP
INC 3 3
POP 
POP
POP
Sample Output 1:
-1
1 6 7 -1
Explanation of sample input 1:
In the first test case,  there is only 1 ‘POP’ query, as the stack initially is empty so we should return -1.

For the second test case, refer the problem statement for an explanation.
Sample Input 2:
1
5 5
PUSH 2
PUSH 3
INC 1 1
INC 2 1
POP
Sample Output 2:
4
Hint

Do as directed.

Approaches (2)
Simulation

The basic idea is to simulate stack using vector/list’.  The PUSH and POP query can be performed in O(1) times, and for the query of type INC ‘K’ ‘Y’, we iterate over the first ‘K’ elements (If exist) and increment them by Y,  it can take O(K) times.

 

The steps are as follows:

  1. Make an empty vector/list ‘STK’.
  2. Make an empty vector/list ‘RESULT’.
  3. Iterate over the queries and for each query and do the following  -:
    1. If the query is of type PUSH ‘X’, then simply check the size of ‘STK’, if it is less than ‘LIMIT’ then append ‘X’ in list/vector ‘STK’.
    2. If the query is of type POP, then if ‘STK’ is empty, append -1 in ‘RESULT’ otherwise, append the last element of ‘STK’ in ‘RESULT’ and then remove the last element of ‘STK’, 
    3. If the query is of type INC ‘K’, ‘Y’,  then run a loop where ‘i’ ranges from 0 to min(‘K’-1, ‘STK.length-1) and for each ‘i’ do ‘STK[i]’ += ‘Y’.
  4. Return ‘RESULT’.
Time Complexity

O(Q*K), where 'Q' is the number of queries and ‘K’ is the maximum number of elements to be incremented in the query of type ‘INC’.

 

The query of type INC processed in O(K) times and there are ‘Q’ queries, In the worst case most of the queries are of type 3  thus it takes at most O(Q*K) time to process all these queries. Thus, the overall time complexity will be O(Q).

Space Complexity

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

 

The size of the vector/list ‘STK’  can go up to O(Q), Thus the space complexity will be O(Q).

Code Solution
(100% EXP penalty)
Queries on Stack
Full screen
Console