Min Stack

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

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.

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)

Naive Simulation

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

Time Complexity

O(N) where N is the no. of operations performed.

All of our operations are doing some constant no. of operations and taking O(1). For each of the operations, we will take O(1) time. Hence the final time complexity will be O(N) for N operations.

Space Complexity

O(N) where N is the no. of operations performed.

We have to store two stacks: “Stack” and “Min”. The size of each of the stacks can be at most N. So each stack will take O(N) space. So total space required = O(N)+O(N) = O(N).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Input 1 :

Sample Input 2 :

Sample Output 2 :