Last Updated: 28 Apr, 2021
Queries on Stack
Moderate
Asked in company
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].
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
Approaches
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:
- Make an empty vector/list ‘STK’.
- Make an empty vector/list ‘RESULT’.
- Iterate over the queries and for each query and do the following -:
- 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’.
- 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’,
- 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’.
- Return ‘RESULT’.
We can optimize the previous approach by keeping a vector/list ADD to track the increments operation, we only increment the value of the element at a time when it ‘POP’. This idea can be implemented as follow -:
- Make an empty vector/list ‘STK’.
- Make two empty vector/list ‘RESULT’, ‘ADD’.
- Iterate over the queries and for each query and do the following -:
- 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’ and append 0 in the list/vector ‘ADD’.
- If the query is of type POP, then if ‘STK’ is empty, append -1 in ‘RESULT’ otherwise, append the last element of ‘STK’ + last element of ‘ADD’ in ‘RESULT’ and then remove the last element of ‘STK’, If the size of ‘ADD’ is more than 1, then increment second last element of ‘ADD’ by the last element of ‘ADD’ and remove the last element of ‘ADD’.
- If the query is of type INC ‘K’, ‘Y’, then If ‘STK’ is not empty do ADD[min(‘K’-1, ‘STK.length-1)] += K.
- Return ‘RESULT’.