New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Min Stack

Contributed by

TanishkTonk

Last Updated: 23 Feb, 2023

Easy

0/40

14 upvotes

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

Auto

Console