Min Stack Problem Solution in C++

In this article, we will provide you the code of the Minimum Value in a Stack using stack in C++. This is the most famous problem asked in the Coding Rounds of many companies like Flipkart, Amazon, Snapdeal, De-Shaw, etc.

Q. You are given N elements and your task is to Implement a Stack in which you can get a minimum element in O(1) time with O(1) space.

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

We earn a commission if you make a purchase, at no additional cost to you.

Steps to Solve the Problem

To implement a stack that can efficiently return the minimum value in O(1) time without using any extra space, you can follow the steps given below:

  1. Create two stacks, one to store the actual values and the other to store the minimum values.
  2. When you push a value onto the stack, check if it’s smaller than or equal to the current minimum value. If it is, push it onto the minimum value stack as well.
  3. When you pop a value from the stack, check if it’s equal to the current minimum value. If it is, pop the minimum value stack as well.
  4. To get the minimum value in O(1) time, simply return the top element of the minimum value stack.

Implementation of the Steps

#include <bits/stdc++.h>
using namespace std;
class Solution{
    int minEle=0;
    stack<int> s;
    public:
    
       /*returns min element from stack*/
       int getMin(){
           
           if(s.size()==0){
               return -1;
           }
           else 
           return minEle;
       }
       
       /*returns poped element from stack*/
       int pop(){
           if(s.size()==0){
               return -1;
           }
           
           else{
               if(s.top()>=minEle){
                   int a=s.top();
                   s.pop();
                   return a;
               }
               else if(s.top()<minEle){
                   int curr=minEle;
                   minEle = 2*minEle-s.top();
                   s.pop();
                   return curr;
               }
           }
           
           
       }
       
       /*push element x into the stack*/
       void push(int x){
           if(s.size()==0){
               s.push(x);
               minEle = x;
           }
           else{
               if(x>=minEle){
                   s.push(x);
               }
               else if(x<minEle){
                   s.push(2*x-minEle);
                   minEle = x;
               }
           }
       }
};
// Driver Code
int main()
{
    MyStack s;
    
      // Function calls
    s.push(3);
    s.push(5);
    s.getMin();
    s.push(2);
    s.push(1);
    s.getMin();
    s.pop();
    s.getMin();
    s.pop();
    s.peek();
  
    return 0;
}

An approach that uses O(1) time and O(1) space complexity.

Leave a Reply