Stack: Get the min element of the stack in O(1) time

Problem Statement:

You need to implement a stack that will return the min element in constant time.

Solution

This problem can be solved in 2 ways:
1. Using 2 stacks
2. Using only 1 stack.

Method 1: Using 2 stacks:

In this method, we maintain 2 stacks.

One stack to insert all the elements and another stack we store all the min stack elements that we encounter while adding the elements in the stack.

Consider below Image:

At every stage we have a smallest element.
So if the new element is less than the current min element, then we push that element into both of the stacks.
Then while popping the element, if the element to be popped is equal to the current min, then we pop from both of the stack.
The element present in top of the second stack, is the new min element in the stack.

Method 2: Using only 1 stack:

In this method we use only 1 stack.

We will have a variable “current_min” that will hold the current min value.

So, if we encounter a new variable that is minimum than the current_min, then we wil push the current_min element into the stack and then push the new variable and change the current_min to the new variable.

During pop operation, if the element to be popped is the current_min, then we pop that element and then take the next element and make it as current_min and then pop that element also.

Example:

the current_min is 3 in below stack.

4
5
3

Now we push(2). Then we first push the current_min element into the stack:

3
4
5
3

Then we push(2) into the stack:

2
3
4
5
3

Then we do pop(), we pop the 2 and then make 3 as current_min and then pop 3 also.

 

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

class Min_Stack_Using_2_stacks {
public:
    stack<int> stk;
    stack<int> min_stack;
    
    void push(int x) 
    {
        if(stk.empty() || x <= min_stack.top())
            min_stack.push(x);
        stk.push(x);
    }
    
    void pop() 
    {
        if(stk.top() == min_stack.top()) 
            min_stack.pop();
        stk.pop();
    }
    
    int top() 
    {
        return stk.top();
    }
    
    int getMin() 
    {
        return min_stack.top();
    }
};

class Min_Stack_Using_1_stack {
public:
    
    stack<int>st;
    int minInStack = INT_MAX;
   
    void push(int x) {
        if(x <= minInStack){
            st.push(minInStack);
            minInStack = x;
        }
        st.push(x);
    }
    
    void pop() {
       int tmp = st.top();
        st.pop();
        if(tmp == minInStack){
            minInStack = st.top();
            st.pop();
        }
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minInStack;
    }
};

int main() 
{
    Min_Stack_Using_2_stacks* minStack = new Min_Stack_Using_2_stacks();
      minStack->push(5);
      minStack->push(6);
      minStack->push(4);
      minStack->push(7);
      minStack->push(3);

      cout<<"The min element is = " <<minStack->getMin()<<endl; 
      minStack->pop();
      cout<<"The min element is = " <<minStack->getMin()<<endl;       

    Min_Stack_Using_1_stack* min_stack = new Min_Stack_Using_1_stack();
      min_stack->push(5);
      min_stack->push(6);
      min_stack->push(4);
      min_stack->push(7);
      min_stack->push(3);

      cout<<"The min element from method 2 = " <<min_stack->getMin()<<endl; 
      min_stack->pop();
      cout<<"The min element from method 2 = " <<min_stack->getMin()<<endl;       
    

    return 0; 
}

Output:

The min element is = 3
The min element is = 4
The min element from method 2 = 3
The min element from method 2 = 4