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

Question

Min Stack

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

Accepted Answer

In this problem I just had to tell them my approach and there was discussion on my approach.

I used two stacks here one to store actual stack elements ( Elements_Stack ) and the other as an extra stack (Min_Stack) to store minimum elements. we maintain push() and pop() operations in such a way that the top of the Min_Stack is provides the minimum element.

Push(int x) // inserts an element x to Min_Stack
1) push x to the Elements_Stack
2) compare x with the top element of the Min_Stack. Let the top element be y.
…..a) If x is smaller than y then push x to the Min_Stack.
…..b) If x is greater than y then push y to the Min_Stack.
int Pop() // removes an element from Min_Stack and return the removed element
1) pop the top element from the Min_Stack.
2) pop the top element from the Elements_Stack and return it.
Step 1 is necessary to make sure that the Min_Stack is updated for future operations.
int getMin() // returns the minimum element from Special Stack
1) Return the top element of the Min_Stack.

Accepted Answer

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

Space Complexity: O(n)Explanation:

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

Time Complexity: O(n)Explanation:

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.

Python (3.5)

'''
    Time Complexity: O(N) 
    Space Complexity:O(N) 

    Where 'N' is the no. of operations performed.
'''

class minStack:

    Stack = []
    Min = []
            
    # Constructor
    def __init__(self):
        pass
    

    # Function to add another element equal to num at the top of stack.
    def push(self, num: int) -> None:

        self.Stack.append(num)
        if len(self.Min) == 0 or self.Min[-1] >= num:
            self.Min.append(num)
        

    # Function to remove the top element of the stack.
    def pop(self) -> int:
    
        if len(self.Min) != 0 and self.Min[-1] == self.Stack[-1]:
            self.Min.pop()

        ret = -1

        if len(self.Stack) != 0:
            ret = self.Stack[-1]
            self.Stack.pop()

        return ret
    

    # Function to return the top element of stack if it is present. Otherwise return -1.
    def top(self) -> int:
    
        ret = -1
        if len(self.Stack) != 0:
            ret = self.Stack[-1]
        
        return ret
    
    
    # Function to return minimum element of stack if it is present. Otherwise return -1.
    def getMin(self) -> int:
    
        ret = -1
        if len(self.Min) != 0:
            ret = self.Min[-1]
        
        return ret

Java (SE 1.8)

/*
    Time Complexity: O(N) 
    Space Complexity:O(N) 

    Where 'N' is the no. of operations performed.
*/

import java.util.Stack;

public class MinStack {

    Stack stack, Min;

    // Constructor
    MinStack() {
        stack = new Stack();
        Min = new Stack();
    }

    // Function to add another element equal to num at the top of stack.
    void push(int num) {
        stack.push(num);
        if (Min.empty() || Min.peek() >= num) {
            Min.push(num);
        }
    }

    // Function to remove the top element of the stack.
    int pop() {
        if (!Min.empty() && Min.peek() == stack.peek()) {
            Min.pop();
        }

        int ret = -1;

        if (!stack.empty()) {
            ret = stack.peek();
            stack.pop();
        }

        return ret;
    }

    // Function to return the top element of stack if it is present. Otherwise
    // return -1.
    int top() {
        int ret = -1;
        if (!stack.empty()) {
            ret = stack.peek();
        }
        return ret;
    }

    // Function to return minimum element of stack if it is present. Otherwise
    // return -1.
    int getMin() {
        int ret = -1;
        if (!Min.empty()) {
            ret = Min.peek();
        }
        return ret;
    }
};

C++ (g++ 5.4)

/*
    Time Complexity: O(N) 
    Space Complexity:O(N) 

    Where 'N' is the no. of operations performed.
*/

class minStack
{
	stack Stack, Min;
	
	public:
		
		// Constructor
		minStack() { }
		
		// Function to add another element equal to num at the top of stack.
		void push(int num)
		{
			Stack.push(num);
			if(Min.empty() || Min.top() >= num){
				Min.push(num);
			}
		}
		
		// Function to remove the top element of the stack.
		int pop()
		{
			if(!Min.empty() && Min.top() == Stack.top()) {
				Min.pop();
			}

			int ret = -1;

			if(!Stack.empty()) {
				ret = Stack.top();
				Stack.pop();
			}

			return ret;
		}
		
		// Function to return the top element of stack if it is present. Otherwise return -1.
		int top()
		{
			int ret = -1;
			if(!Stack.empty()){
				ret = Stack.top();
			}
			return ret;
		}
		
		// Function to return minimum element of stack if it is present. Otherwise return -1.
		int getMin()
		{
			int ret = -1;
			if(!Min.empty()) {
				ret = Min.top();
			}
			return ret;
		}
};

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

For Example:

Input Format:

Output Format:

Note:

Constraints -

Top Jio Platforms Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Jio Platforms Software Developer