Min Stack

Easy

0/40

Contributed by

95 upvotes

Asked in companies

Problem statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

1. Push(num): Push the given number in the stack.
2. Pop: Remove and return the top element from the stack if present, else return -1.
3. Top: return the top element of the stack if present, else return -1.
4. getMin: Returns minimum element of the stack if present, else return -1.

For Example:

For the following input: 
1
5
1 1
1 2
4
2
3

For the first two operations, we will just insert 1 and then 2 into the stack which was empty earlier. So now the stack is => [2,1]
In the third operation, we need to return the minimum element of the stack, i.e., 1. So now the stack is => [2,1]
For the fourth operation, we need to pop the topmost element of the stack, i.e., 2. Now the stack is => [1]
In the fifth operation, we return the top element of the stack, i.e. 1 as it has one element. Now the stack is => [1]

So, the final output will be: 
1 2 1

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single integer ‘N’, denoting the no. of the operations.

The next ‘N’ lines of each test case contain either of the operations in the following format: - 
Push -> two space-separated integers, 1 and ‘X’ like “1 X”. We need to push ‘X’ on top of the stack.
Pop -> single integer 2. We need to remove the topmost element from the stack.
Top -> single integer 3. We need to return the topmost element from the stack.
getMin -> single integer 4, We need to return the minimum element of the stack if present and 0 otherwise.

Output Format:

For each test case, print the results of the operations performed on the stack separated by spaces.

Print output of each test case in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints -

1 ≤ T ≤ 1000
1 ≤ N ≤ 100000
ΣN ≤ 200000
1 ≤ X ≤ (10^9)

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

1 2 1
13 -1 -1

Explanation For Sample Input 1 :

For First Case - Similar to the example explained above. 

For Second Case - 
For the first operation, we will just insert 13 into the stack which was empty earlier. So now the stack is => [13]
In the second operation, we need to remove the topmost element 13 and return it for printing. Now the stack is => [] (empty)
For the third operation, we need to return the topmost element of the stack. As the stack is empty we will return -1. Now the stack is => [] (empty)
 In the fourth operation, we return the minimum element of the stack if it is not empty, i.e. -1 as it has no elements. Now the stack is => [] (empty)

Sample Input 2 :

Sample Output 2 :

-1 -1 4
45 19 45 19

Console