Design a stack that returns the minimum element in constant time.

Problem Statement:

You need to design a stack that returns the minimum element from the stack in constant time.

Solution

For solving this problem we will use 2 stack.

1. Push Operation:

1. Push the element in to the first stack, and push into the 2nd stack if the stack is empty or new element is less than or equal to the current top element of the 2nd stack.

2. Pop Operation:

1. Remove the top element from the main stack, and remove the element from the 2nd stack if it is equal to the current min element.

2. It means, if both the main stack and 2nd stack is same.

3. Once we remove the element form 2nd stack, the next minimum number appears on the top of 2nd stack.

3. Get min Operation:

The top of the 2nd array will always returns the min number.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;

class my_stack
{
    stack<int> s;       // main stack to store elements
    stack<int> temp;     // temp stack to store minimum elements
 
public:
    void push(int x)
    {
        s.push(x);
 
        if (temp.empty()) 
        {
            temp.push(x);
        }
        else {
            if (temp.top() >= x) 
            {
                temp.push(x);
            }
        }
    }
 
    int pop()
    {
        if (empty())
        {
            cout << "Stack underflow!!" << endl;
            return -1;
        }
 
        int top = s.top();
        s.pop();
 
        if (top == temp.top()) {
            temp.pop();
        }
 
        return top;
    }
 
    int top() {
        return s.top();
    }
 
    int size() {
        return s.size();
    }
 
    bool empty() {
        return s.empty();
    }
 
    int get_min()
    {
        if (temp.empty())
        {
            cout << "Stack underflow!! ";
            return -1;
        }
 
        return temp.top();
    }
};
 
int main()
{
    my_stack s;
 
    s.push(7);
    cout << s.get_min() << endl;
 
    s.push(8);
    cout << s.get_min() << endl;  
 
    s.push(9);
    cout << s.get_min() << endl; 
 
    s.push(6);
    cout << s.get_min() << endl; 
 
    s.push(4);
    cout << s.get_min() << endl; 
 
    s.pop();
    cout << s.get_min() << endl; 
 
    s.push(11);
    cout << s.get_min() << endl;
 
    s.pop();
    cout << s.get_min() << endl;
 
    s.pop();
    cout << s.get_min() << endl; 
 
    return 0;
}

Output:

7
7
7
6
4
6
6
6
7