The Brute Force Approach
The simplest solution that comes to mind is to use another stack to keep track of the minimum element so far. And adjust it for each push and pop operation.
Let's see how we can put it into action...
Algorithm
- To solve the problem, you must create two separate stacks let’s say (s1 and s2)
- The first stack (s1) would contain the actual elements, and the second stack (s2) would contain the current stack's minimum element.
- When we need to push an element into the stack, we must first determine whether or not the stack (s1) is empty. If the stack (s1) is empty, we just push the element into both stacks.
- Otherwise, push the element in the stack (s1) and take the minimum of the top of the stack (s2) and the current element and push it in the stack s2.
Remember to keep the following factors in mind before calling the functionalities:
- For POP(), first determine whether the stack (s1) is empty or not, if the stack is not empty save and pop the top of the stack (s1). Else return ‘-1.' Also remove the top element from the stack(s2) only if it is the minimum element
- For TOP(), see if the stack (s1) is empty. If the stack is empty, return ‘-1'. Otherwise, return the top of the stack (s1).
- For getMin(): Check if the stack is empty before calling getMin(). Return ‘-1' if the stack is empty. Otherwise, return the top of stack (s2).
- If the stack is empty, ISEMPTY() returns True; otherwise, it returns False.
Implementation Of Brute Force Approach
#include <bits/stdc++.h>
using namespace std;
class MinStack
{
//Primary stack to store elements
stack<int> s1;
// temporary Stack to store minimum elements
stack<int> s2;
public:
void push(int x)
{
cout <<"Push element: "<< x << endl;
s1.push(x);
// if the tempStack is empty, push the given element into it
if (s2.empty())
{
s2.push(x);
}
else
{
// push the given element into the tempStack
// if it is less than or equal to the current minimum
if (s2.top() >= x)
{
s2.push(x);
}
}
}
int pop()
{
if (empty())
{
cout << "Stack is Empty!!" << endl;
return -1;
}
int top = s1.top();
s1.pop();
// remove the top element from the tempStack
// only if it is the minimum element
if (top == s2.top())
{
s2.pop();
}
return top;
}
int top() {
return s1.top();
}
// Returns the size of the stack
int size() {
return s1.size();
}
bool empty() {
return s1.empty();
}
// Function to return the minimum element from the stack in //constant time
int getMin()
{
if (s2.empty())
{
cout << "Stack is Empty!! ";
return -1;
}
return s2.top();
}
};
int main()
{
MinStack s1;
s1.push(6);
s1.push(7);
s1.push(8);
cout <<"The minimum element is: "<< s1.getMin() << endl;
s1.push(5);
s1.push(3);
cout <<"The minimum element is: "<< s1.getMin() << endl;
cout <<"Popped element: "<< s1.pop() << endl;
s1.push(10);
cout <<"The minimum element is: "<< s1.getMin() << endl;
cout <<"Popped element: "<< s1.pop() << endl;
cout <<"Popped element: "<< s1.pop() << endl;
cout <<"The minimum element is: "<< s1.getMin() << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output-
Push element: 6
Push element: 7
Push element: 8
The minimum element is: 6
Push element: 5
Push element: 3
The minimum element is: 3
Popped element: 3
Push element: 10
The minimum element is: 5
Popped element: 10
Popped element: 5
The minimum element is: 6
Complexity Analysis
Time Complexity
The time complexity is as follows:
push(): O(1) - As insertion in a stack takes constant time.
pop(): O(1) - As deletion of the top element in a stack takes constant time.
top(): O(1) - Constant time is required.
getMin(): O(1) - As we have used an auxiliary stack that has it’s top as the minimum element.
isEmpty(): O(1) - Constant time is required.
Space Complexity
The space complexity is O(N) as auxiliary space is required to keep track of the minimum element.
Read More - Time Complexity of Sorting Algorithms
The Optimized Approach
Another way to solve this problem is by using the optimized approach by storing the smallest element of our stack as discovered in a special variable and returning the same at the end of the entire program of the minimum stack. But there’s a big elephant in the room! What if the minimum element is popped off? What do we do then?
Don’t worry, let's see the algorithm and then explanation why this approach actually works!!
Algorithm
Here, we will store the smallest element encountered at any point in time in a variable called ‘MinEle'
FOR PUSH (x) Operation where x is the element to be inserted, We have 3 cases:
Case 1. IF THE STACK IS EMPTY
Simply insert the x into the stack and change the MinEle to x.
Case 2. IF STACK IS NOT EMPTY AND x>=STACK TOP VALUE
Simply insert the x into the stack.
Case 3. IF THE STACK IS NOT EMPTY AND x < STACK TOP VALUE
Push (2 * x - MinEle) into the stack and change the value of 'MinEle' to x.
For POP () operation
Case 1: Determine whether or not the stack is empty. We return ‘-1' if the stack is empty.
Case 2: If the stack’s top value >= MinEle
Simply remove the top value from the stack; the minimum value will remain unchanged.
Case 3: If the stack's top value < MinEle
Here top is the minimum element.
Thus to handle the case where the minimum element is removed, we would need to save the previous minimum element.
So, update the MinEle = (2 * MinEle - stack’s top value)
For TOP () operation
Case 1: Determine whether the stack is empty. If the stack is empty, Return -1.
Case 2: Determine whether the last inserted element of the stack is less than MinEle. If so, we will return MinEle. Otherwise, we will return the last element pushed into the stack.
For getMin() operation
We will simply return the value of MinEle
Why does this approach work?
Taking the approach under consideration, we get two simple scenarios:
- (2 * x - MinEle ) < MinEle and,
- When the top element is minimum and it is popped, the previous minimum element was restored using (2 * MinEle - stack’s top value)
Let’s Solve this using Simple Mathematics:
For Point 1:
x < MinEle which proves that x - MinEle < 0
//where x is the current element to be inserted.
//Adding x to both sides
We conclude that:
2 * x - MinEle < x
For Point 2:
//For simplicity let us take current element to be inserted as e, current minElement as m, previous minElement as p and n for new minElement
We know y was pushed as 2*e - p when e < current minElement
y = 2*e - p
// minElement was updated to e
m = e
n = 2*m - y
= 2*e - (2*e - p)
= p
So the new minElement is equal to the previous minElement. Hurrah! This is what we wanted.
Implementation of Space Optimized Approach
// C++ program to implement brute force approach
// getMin() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
struct MyStack
{
stack<int> stc;
int MinEle;
//printing the minimum stack value
void getMin()
{
if (stc.empty())
cout << "Stack is empty\n";
// variable MinEl stores the minimum stack element
// of the stack.
else
cout << "Minimum Element in the stack is: "
<< MinEle<< "\n";
}
//printing the top most element of the stack
void peek()
{
if (stc.empty())
{
cout << "Stack is empty ";
return;
}
int top = stc.top();
cout << "Top Most Element is: ";
(top < MinEle) ? cout << MinEle: cout << top;
}
void pop()
{
if (stc.empty())
{
cout << "Stack is empty\n";
return;
}
cout << "Top Most Element Removed: ";
int top = stc.top();
stc.pop();
if (top < MinEle)
{
cout << MinEle<< "\n";
MinEle= 2 * MinEle- top;
}
else
cout << top << "\n";
}
void push(int x)
//here x is the element to be pushed
{
if (stc.empty())
{
MinEle= x;
stc.push(x);
cout << "Push Element: " << x << "\n";
return;
}
if (x < MinEle)
{
stc.push(2 * x - MinEle);
MinEle= x;
}
else
stc.push(x);
cout << "Push Element: " << x << "\n";
}
};
int main()
{
MyStack stc;
stc.push(3);
stc.push(5);
stc.getMin();
stc.push(2);
stc.push(1);
stc.getMin();
stc.pop();
stc.getMin();
stc.pop();
stc.getMin();
return 0;
}
You can also try this code with Online C++ Compiler
Output-
Push Element: 3
Push Element: 5
Minimum Element in the stack is: 3
Push Element: 2
Push Element: 1
Minimum Element in the stack is: 1
Top Most Element Removed: 1
Minimum Element in the stack is: 2
Top Most Element Removed: 2
Minimum Element in the stack is: 3
Complexity Analysis
Time Complexity
push(): O(1) - Constant time is required.
pop(): O(1) - Constant time is required.
top(): O(1) - Constant time is required.
getMin(): O(1) - Constant time is required as we are storing the min element in a special variable.
isEmpty(): O(1) - Constant time is required.
Space Complexity
O(1), No extra space is required.
If you've read this far, then without further ado, let’s try to submit the “Minimum Stack” problem on Coding Ninjas Studio and get it accepted right away.
Must Read Stack Operations
Frequently Asked Questions
What is a stack?
A stack is an abstract data structure that constitutes a collection of elements.It implements the “Last In First Out” mechanism.
What is the minimum stack?
A minimum stack can be defined as a stack that is eligible for performing 3 operations. The three operations are as follows:
Push() - To add an element to the stack.
Pop() - To remove an element from the stack.
min() - To return the current minimum stack value.
How many minimum queues are needed to implement a stack?
Two queues are required to implement the stack.
What is the time complexity of an operation in a minimum stack?
The time complexity of all the operations performed on a minimum stack is O(1).
Conclusion
In this blog, we learned about returning the minimum value in a Stack in O(1) time-
- We started with the brute force approach, where we took two stacks, one storing the current number and the other storing the minimum stack value.
- The second approach was the space optimization approach where we used an extra variable to store the minimum element of the stack.
There are a lot of other problems related to stack which are frequently asked in interviews, some are:
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
You can also consider our Mern Stack Course to give your career an edge over others.
If you liked this blog, share it with your friends.
136+ registered 
