Last Updated on September 22, 2023 by Mayank Dham
In this article, we will learn what is Min Stack and what are the different ways to implement the min stack.
What is Min Stack?
The Min Stack is a special type of stack that support all the stack operations such as push(), pop(), isEmpty(), and isFull(). In addition, Min Stack also supports one additional function getMin(), which is used to retrieve the minimum element from the stack that is why it is also called the minimum stack.
Lets understand what is the min stack using an example.
stack = [30, 10, 50, 20, 40]For this stack, if we call getMin() function then it will return 10.
Now, let’s see how a stack looks after performing the pop() operation two times.
stack = [10, 50, 20, 40] ( 1st pop() operation)
stack = [50, 20, 40] (2nd pop() operation )If we call getMin() function this time then it will return 20.
Different Ways to Implement Min Stack:
We already know what is the min stack. Now. let’s see how to implement the min stack using various approaches.
Approach 1:
In this approach, we store the pair as the current value and the value of the minimum so far. This means the first element of the pair will store the value and the second element will store the minimum till now. Let’s understand this approach with an example dry run.
Dry run:
Initial stack=[]
Operation: push(20)
stack=[(20,20)]
Here, we have inserted pair (20,20) into the stack, the first element is the value and the second value is the minimum stack value till now.Operation: push(30)
stack=[(30,20), (20,20)]
Here, we have inserted pair (30,20) into the stack, the first element is the value (30) and the second value is the minimum stack value(20) till now.Operation: push(10)
stack=[(10,10), (30,20), (20,20)]
Here, we have inserted pair (10,10) into the stack, the first element is the value (10) and the second value is the minimum stack value(10) till now.Operation: push(40)
stack=[(40,10), (10,10), (30,20), (20,20)]
Here, we have inserted pair (40,10) into the stack, the first element is the value (40) and the second value is the minimum stack value(10) till now.
// java program to implement min stack
import java.io.*;
import java.util.*;
class Pair {
int x, y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
class MinStack {
Stack < Pair > st;
public MinStack() {
st = new Stack < > ();
}
public void push(int x) {
int min;
if (st.isEmpty()) {
min = x;
} else {
min = Math.min(st.peek().y, x);
}
st.push(new Pair(x, min));
}
public int pop() {
return st.pop().x;
}
public int top() {
return st.peek().x;
}
public int getMin() {
return st.peek().y;
}
}
class PrepBytes {
public static void main(String[] args) {
MinStack minStack=new MinStack();
minStack.push(20);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
minStack.push(30);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
minStack.push(10);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
minStack.push(40);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
System.out.println("Minimum element after pop("+minStack.pop()+"): "+minStack.getMin());
System.out.println("Minimum element after pop("+minStack.pop()+"): "+minStack.getMin());
}
} Output:
Minimum element after push(20): 20
Minimum element after push(30): 20
Minimum element after push(10): 10
Minimum element after push(40): 10
Minimum element after pop(40): 10
Minimum element after pop(10): 20Time Complexity: O(1)
Space Complexity: O(2N)
Approach 2:
In this approach, we will take an extra variable to store the minimum value till now. So, if we want to push a new value into the stack then we will directly insert that value into the stack and update the value of that extra variable.
Lets see how to implement a particular operation of the min stack.
Push():
To push a new element into the stack, first, we will check whether the value of the new element is less than the min value till now. If the value is smaller then we will push the modified value which is (2*value – min) into the stack and we will update the min value to the value of the new element. If the value is not smaller then we will push as it is.
Pop():
While performing pop, we will check if the top value is less than min or not, If it is lesser than min then we must update our min to its previous value. In order to do that min = (2 * min) – (modified value) and we will pop the element.
getMin():
We can directly return the value of the min.
Top():
To perform the top() operation, we know that it is a modified value. We will check if the top value is less than the min, If it is lesser, then we will return the min as the top value.
// java program to implement min stack
import java.io.*;
import java.util.*;
class MinStack {
Stack < Integer > st = new Stack < Integer > ();
int mini;
public MinStack() {
mini = Integer.MAX_VALUE;
}
public void push(int val) {
if (st.isEmpty()) {
mini = val;
st.push(val);
} else {
if (val < mini) {
st.push(2 * val - mini);
mini = val;
} else {
st.push(val);
}
}
}
public int pop() {
if (st.isEmpty()) return -1;
int val = st.pop();
if (val < mini) {
int tmp=mini;
mini = 2 * mini - val;
return tmp;
}
return val;
}
public int top() {
int val = st.peek();
if (val < mini) {
return mini;
}
return val;
}
public int getMin() {
return mini;
}
}
class PrepBytes {
public static void main(String[] args) {
MinStack minStack=new MinStack();
minStack.push(20);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
minStack.push(30);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
minStack.push(10);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
minStack.push(40);
System.out.println("Minimum element after push("+minStack.top()+"): "+minStack.getMin());
System.out.println("Minimum element after pop("+minStack.pop()+"): "+minStack.getMin());
System.out.println("Minimum element after pop("+minStack.pop()+"): "+minStack.getMin());
}
} Output:
Minimum element after push(20): 20
Minimum element after push(30): 20
Minimum element after push(10): 10
Minimum element after push(40): 10
Minimum element after pop(40): 10
Minimum element after pop(10): 20Time Complexity: O(1)
Space Complexity: O(N)
FAQs
1) What is the major difference between the stack and the min stack?
The Min stack can perform operations such as push(), pop(), isEmpty(), top(), and getMin(). While the stack does not have getMin() operation.