Min Stack Problem
Difficulty : Easy
Asked in : Amazon, Microsoft, Yahoo, Adobe
Understanding the Problem:
Given Problem is to design a special stack data structure such that it supports following operations in constant O(1) time complexity.
 top(): which will get the top element of the stack.
 getMin(): returns the minimum elements of the stack (Currently present, deleted ones are not taken into account).
 push(element): pushes an element "element" in the stack.
 pop(): removes the element present at the top from the stack.
For Example:
Input:
stck = minStack() //Create an object of your special stack
stck.push(2)
stck.push(4)
stck.top() > returns 4 as 4 is at the top(last inserted element)
stck.getMin() > returns 2 as it is the current minimum
stck.pop()
stck.push(1)
stck.getMin() > returns 1 as now it is the minimum element.
Possible questions to ask the interviewer: →
 Can I use extra space for solving this? ( Ans: Yes, you can. Try to optimise it though. Make sure time complexity is constant. )
 What will be the input format? ( Ans: The input provided will be a series of function calls like push(), pop(), top(), getMin(), etc. )
You can try solving this problem here and then move on to the solution part.
Solutions
So here we are going to discuss two possible solutions to solve this problem. Both the solutions will be of constant time complexity. However, the second solution will be more optimised in terms of space and will be testing your mathematical skills. Excited? Let’s see both the solutions in details.
 Solution 1: Using Extra Space
 Solution 2: Using Constant Space
Using Extra Space
This approach will use an array which will be used to store elements at every point whenever its value is less than the top element of the stack. So we will keep checking every time before pushing the element into the stack(
push()
operation) if its value is smaller than the last element inserted into the array or not. If yes, we will add this element to the array as well as to the stack. Else, we will only add the element to the stack.
In case of the
pop()
operation, we will check if the element to be deleted(top element) is the same as the last element inserted to the array. If this is the case, we have to delete this element from both the places(stack and array) so that the last element of the array now will point to the current minimum element.
The
top()
operation will simply return the last element present in the stack and the
getMin()
operation will return the last element of the array.
Solution steps
 We will create an array to store all the current minimum values so to access it accordingly.
 During the push operation, we will push the element ‘elem’ directly to the stack and array if the stack is empty. If not, then we will compare the ‘elem’ with the last inserted element in the stack. If it is smaller we will push it to both stack and array. Else, will push only into the stack.
 In the pop operation, we will check if the last inserted element is same as the last pushed element in the array. If yes, we will need to delete both of them so that the last element of the array will now be pointing to the current minimum element after the deletion of this(top) element.
 For top operation and getMin operation, we simply need to return the last element of the stack and the array respectively.
Pseudocode
class MinStack {
public:
vector <int> stack
vector <int> minArray
MinStack() {
//Constructor
}
//Push operation
void push(int elem) {
if(!minArray.empty())
{
if(elem <= minArray.back())
minArray.push_back(elem)
}
else
minArray.push_back(elem)
stack.push_back(elem)
}
//Pop operation
void pop() {
if(stack.back() == minArray.back())
{
minArray.pop_back()
}
stack.pop_back()
}
//Top operation
int top() {
if(!stack.empty()) //Simply returns top element from stack
return stack.back()
else
return 1
}
//getMin operation
int getMin() {
if(!minArray.empty()) //Simply returns last element from //minArray
return minArray.back()
else
return 1
}
}
Note : Vectors are dynamic arrays supported by C++ STL. push_back(T elem) will push an element to vector, pop_back() will delete the last element, empty() will check if the vector is empty or not and back() will give the last element of the vector. For getting more idea: — Go here . You can find its subtitute in whaever language you code.
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(N)
Critical ideas to think!
 What if instead of having an array, we keep only one variable for minimum Element and keep updating it with every push operation if the new element is smaller than the current minimum element? Do you see any issues in this approach? (Think and comment down below)
Using Constant Space
In this approach instead of using an array and increasing the space complexity, we will rather use a variable
minElement
which will store the current minimum element of the stack at every point.
Have you thought about the above given critical idea? Hmm, the problem is when we have to
pop
this
minElement
from the stack. How will we update the minElem then?
To solve this issue, we will use a very different idea. The idea is to whenever we will encounter an element smaller than minElement instead of pushing the ‘elem’ to the stack and updating
minElement
, we will instead push (2*elem  minElement) to the stack and update
minElement
with ‘elem’.
During the pop operation, if we encounter any element smaller than
minElement
, we will know it is the same altered element that we pushed and it’s time to modify our
minElement
. We will return the
minElement
and update our
minElement
with (2*minElement  top Element). Too many maths involved here. Let's move on to the solution steps.
Solution steps

We will modify our push operation such that it simply pushes the element and update
minElement
if the stack is empty. Otherwise, it will compare the ‘elem’ with theminElement
. If smaller, we will push (2*elemminElement) instead to the stack and updateminElement
with ‘elem’. 
Similarly, we will modify our pop operation so that whenever we will encounter that that top element to be deleted is less than
minElement
, we will update our minElement with (2*minElementtop element). 
For top operation, we will check if the last inserted element of the stack is smaller than
minElement
. If yes, we will returnminElement
. Else we will return the last element pushed into the stack. (Think why?) 
For
getMin
operation, we will simply return the value ofminElement
.
Illustration for this solution
We will take the above approach and will insert 2, 4, 1 into the stack.
Insert 2 →stack is empty simply push 2. minElement is 2
Insert 4 → 4 > 2, push 4 to stack. minElement is still 2.
Insert 1, 1 < 2, push (2*elem — minElement) i.e. 4 to the stack. minElement is 1.
Pop top element i.e. 4, it is the time to change our minElement. minElement will be 2*minElement top Element i.e. 2*1(4) = 2.
Wow, that is exactly what we want.
Why this approach works?
If you have observed, we have taken two assumptions:
 (2*elemminElement) < minElement and,

previous
minElement
was (2*minElement  y) which was used to make newminElement
after deleting y, where y is the smaller number than current minElement that is to be deleted(pop operation).
Let us try to prove this using mathematics:
Proving our point (i)
For simplicity let us take elem as e, minElement as m, previous minElement as p
e < m which implies em < 0
//Adding e to both sides
2*e  m < e
Thus, we can conclude:
2*elem  minElement < elem
Proving our point (ii)
//For simplicity let us take elem as e, 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 previous minElement.
Hurrah! This is what we wanted.
Pseudocode
class MinStack {
public:
vector <long int> stack
long int minimum
MinStack() {
//Constructor
}
//Push Operation
void push(int x) {
long y = (long)x
if(!stack.empty())
{
if(y<minimum) {
stack.push_back(2*y  minimum)
minimum = y
}
else
stack.push_back(y)
}
else {
stack.push_back(y)
minimum =y
}
}
//Pop Operation
void pop() {
if(stack.back() < minimum)
{
minimum = 2*minimum  stack.back();
stack.pop_back()
}
else
stack.pop_back()
}
//Top Operation
int top() {
if(!stack.empty())
if(stack.back() < minimum)
return minimum
else
return stack.back()
else
return 1
}
//getMin Operation
int getMin() {
return minimum
}
};
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(1)
Critical ideas to think!
 Can you think of problems that can be solved using a similar approach? Think and implement problems based on this approach.
Comparison Table for Above Solutions
Suggested Problems to Solve
 Find the maximum element in the Stack in constant time.
 Find duplicates in an array in O(N) time and constant space.
 Clone a stack without using extra space.
 Design a data structure that supports insert, delete, search and getRandom in constant time.
 Merge two sorted arrays in constant space.
Happy Coding!!!