Min Stack

Posted: 22 Jan, 2022
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

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
Approach 1

The basic idea is to store two stacks. One for regular stack and one for storing prefix minimums of our regular stack. We store values at which our minimum changes so that those values are stored and can be accessed later when we pop elements on top of it. We just return the top value of Min stack whenever we are asked getMin(). The implementation details are depicted in the following algorithm.

 

Algorithm: 

 

push(num)

Function arguments - a no. num which is to be inserted on top of the stack.

  • Push num into the regular stack
  • If Min stack is empty OR num ≤ top of Min stack
    • Push num into Min stack

 

pop()

Returns data that is popped or -1 if the stack was already empty

  • If Min stack is not empty AND top of Min stack = top of the regular stack
    • Pop top element of Min stack
  • ret = -1
  • If the regular stack is not empty
    • ret = Top of the regular stack
    • Pop top of the regular stack
  • Return ret

 

top()

Returns the value of node on top of the stack or -1 if the stack was already empty

  • ret = -1
  • If the regular stack is not empty
    • ret = Top of the regular stack
  • Return ret

 

getMin()

Returns the minimum element of the stack if it exists and -1 otherwise.

  • ret = -1
  • If the min stack is not empty
    • ret = top of Min stack
  • Return ret
Try Problem