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.

Pseudo-code

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 the minElement. If smaller, we will push (2*elem-minElement) instead to the stack and update minElement 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*minElement-top element).
• For top operation, we will check if the last inserted element of the stack is smaller than minElement. If yes, we will return minElement. Else we will return the last element pushed into the stack. (Think why?)
• For getMin operation, we will simply return the value of minElement.

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*elem-minElement) < minElement and,
• previous minElement was (2*minElement - y) which was used to make new minElement 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 e-m < 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.

Pseudo-code

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!!!