Home Â» Technical Interview Questions Â» Stack Interview Questions Â» Min Stack

# Min Stack

In min stack problem we have to design a stack to implement the following functions efficiently,
push(x) –> Push an element x to the stack
pop() –> Removes the item on top of stack
top() –> Return the element at top of stack
getMin() –> Return the minimum element present in the stack

Input:
Push -2
Push 0
Get Min
Push -3
Pop
Top
Get Min
Output:
-2

-2

## Algorithm for Min Stack

push, pop, and top method are similar to a normal stack, but to get the minimum element present in the stack we use one more stack that stores the minimum value till every element.

Let the first stack be st and second stack be minSt, then

### push(x)

1. Push x to the stack st.
2. If minSt is empty or if the top of minSt is greater than x push x to minSt.
3. Else push the top of minSt to minSt again.

Time Complexity=O(1)Â
Space Complexity =O(1)

### pop()

Pop an element from stack st and also from stack minSt.

Time Complexity=O(1)Â
Space Complexity=O(1)

### top()

Return the top of stack st.

Time Complexity=O(1)Â
Space Complexity=O(1)

### getMin()

Return the top of stack minSt.

Time Complexity=O(1)Â
Space Complexity=O(1)

Overall Space Complexity = O(n)Â
where n is the maximum number of elements pushed into the stack at a time.

## Explanation for Min Stack

Consider the example above,
Initialize two stack st and minSt.
st = null and minSt = null

1. Push (-2)
st= (-2) and minSt= (-2)
2. Push 0
st= 0 -> (-2) and minSt= (-2) -> (-2)
3. getMin
Top of minSt = (-2), return (-2)
4. Push (-3)
st = (-3) -> 0 -> (-2) and minSt= (-3) -> (-2) -> (-2)
5. Pop
st = 0 -> (-2) and minSt = (-2) -> (-2)
6. Top
Top of stack st is 0, return 0.
7. getMin
Top of stack minSt is (-2), return (-2).

See the image below for clarification.

## JAVA Code for Min Stack

```import java.util.Stack;

public class MinStack {
private static Stack<Integer> st;
private static Stack<Integer> minSt;

private static void push(int x) {
// Push x to stack st
st.push(x);
// If minSt is empty or if top of minSt is greater than x push x to minSt.
if (minSt.isEmpty() || minSt.peek() > x) {
minSt.push(x);
} else {
// Else push top of minSt to minSt again.
minSt.push(minSt.peek());
}
}

private static void pop() {
// Pop element from st and minSt
st.pop();
minSt.pop();
}

private static int top() {
return st.peek();
}

private static int getMin() {
return minSt.peek();
}

public static void main(String[] args) {
// Initialise st and minSt
st = new Stack<>();
minSt = new Stack<>();

// Example
push(-2);
push(0);
System.out.println(getMin());
push(-3);
pop();
System.out.println(top());
System.out.println(getMin());
}
}```
```-2
0
-2```

## C++ Code for Min Stack

```#include<bits/stdc++.h>
using namespace std;

stack<int> st;
stack<int> minSt;

void push(int x) {
// Push x to stack st
st.push(x);
// If minSt is empty or if top of minSt is greater than x push x to minSt.
if (minSt.empty() || minSt.top() > x) {
minSt.push(x);
} else {
// Else push top of minSt to minSt again.
minSt.push(minSt.top());
}
}

void pop() {
// Pop element from st and minSt
st.pop();
minSt.pop();
}

int top() {
return st.top();
}

int getMin() {
return minSt.top();
}

int main() {
// Example
push(-2);
push(0);
cout<<getMin()<<endl;
push(-3);
pop();
cout<<top()<<endl;
cout<<getMin()<<endl;

return 0;
}```
```-2
0
-2```

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek was able to crack Microsoft after practicing questions from TutorialCup