Get Minimum Element from Stack

Last Updated on May 25, 2023 by Prepbytes

Get minimum element from stack is a common problem in computer science. A stack is a data structure that follows the Last-In-First-Out (LIFO) principle, where elements are added and removed from the top of the stack. While accessing and removing elements from the top of the stack is straightforward, finding the minimum element poses a challenge since the stack does not inherently provide direct access to it.

How to get Minimum Element from Stack

Design a Data Structure that performs the Stack operation like push(), pop() and one more operation getMin(), getMin() function should return the minimum element from the stack. The interviewer also told him that all these operations must be in O(1) time and use only stack data structure.

1. push(x) – Push element x onto stack.
2. pop() – Removes the element on top of the stack.
3. top() – Get the top element.
4. getMin() – Get the minimum element in the stack.

See original problem statement here

STACK DATA STRUCTURE

An Abstract Data Type (ADT) that is often used in most programming languages is a stack. It is called a stack because it functions like a stack in the real world, such as a deck of cards, a pile of dishes, etc.

A LIFO data structure is a stack. The acronym LIFO means last-in, first out. In this case, the piece that was added or inserted last is the one that gets accessible first. Insertion operations are referred to as PUSH operations and removal operations as POP operations in the context of stacks.

The use of an array, structure, pointer, or linked list can be used to implement a stack. A stack may have a feeling of dynamic resizing or it may have a fixed size.

PUSH Operation:
Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.

POP Operation:
Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.

GET MINIMUM:
Retrieve the minimum element in the stack.

TOP :
Get the top element.

Code Implementation

#include 
int main()
{
    int q;
    scanf("%d",&q);
    int stack[q],stackmin[q];
    int top=-1,topmin=-1;
    while(q--)
    {
        int x;scanf("%d",&x);
        if(x==1)
        {
            int y;scanf("%d",&y);
            stack[++top]=y;
            if(topmin==-1)
              stackmin[++topmin]=y;
            else if(y<=stackmin[topmin])
                stackmin[++topmin]=y;
        }
        else if(x==2)
        {
            if(top==-1)
                printf("-1\n");
            else
            {
                if(stack[top]==stackmin[topmin])
                    topmin--;
                //printf("%d\n",stack[top]);
                top--;}
        }
        else if(x==3)
        {
            if(top==-1)
                printf("-1\n");
            else
                printf("%d\n",stack[top]);}
            else
            {
                if(top==-1)
                    printf("-1\n");
                else
                    printf("%d\n",stackmin[topmin]);}
    }
    return 0;
 }

#include 
using namespace std;
stack s;
int minEle;
void Push(int x)
{
    if (s.empty()) {
        s.push(x);
        minEle = x;
    }
    else if (x > minEle) {
    s.push(x);
    }
    else {
        s.push(2 * x - minEle);
        minEle = x;
    }
}
void Pop()
{
    if (s.empty()) {
        cout << -1 << '\n';
    }
    else{
        int top = s.top();
        if (top < minEle)
            minEle = 2 * minEle - top;
        s.pop();
     }
}
int minimum()
{
    if(!s.empty())
        return minEle;
    else
        return -1;
}
int Top()
{
    if(s.empty())
        return -1;
    else{
    int t = s.top(); // Top element.
    // If t < minEle means minEle stores
    // value of t.
    return (t < minEle)? minEle:t;
    }
}   
int main()
{
    int q;
    cin>>q;
    while(q--){

    int k;
    cin>>k;
    if(k==1){
        int x;
        cin>>x;
        Push(x);
    }

    else if(k==2)
        Pop();
    else if(k==3)
        cout<


						 

import java.util.*;
class solution{
   static int minEle;
   static Stack  s=new Stack<>();
   static void Push(int x)
   {
       if (s.isEmpty()==true) {
           s.push(x);
           minEle = x;
       }
       else if (x > minEle) {
           s.push(x);
       }
       else {
           s.push(2 * x - minEle);
           minEle = x;
       }
   }
   static void Pop()
   {
       if (s.isEmpty()==true) {
           System.out.println("-1");
       }
       else{
           int top = s.peek();
           if (top < minEle)
               minEle = 2 * minEle - top;
           s.pop();
       }
   }
   static int minimum()
   {
       if(!s.isEmpty()==true)
           return minEle;
       else
           return -1;
   }
   static int Top()
   {
       if(s.isEmpty()==true)
           return -1;
       else{
       int t = s.peek(); // Top element.
       // If t < minEle means minEle stores
       // value of t.
       return (t < minEle)? minEle:t;
       }
   }
   public static void main (String[] args) {
       Scanner sc=new Scanner(System.in);
       int q=sc.nextInt();
       while(q-->0){
           int k=sc.nextInt();
           if(k==1){
               int x=sc.nextInt();
               Push(x);
           }

           else if(k==2)
               Pop();
           else if(k==3)
               System.out.println(Top());
           else if(k==4)
            System.out.println(minimum());     
       }
       }
}

Conclusion
The "Minimum Element Stack" or "Min Stack" approach provides an efficient solution to retrieve the minimum element from a stack. By maintaining an additional stack, the min stack, alongside the main stack, we can keep track of the minimum element at each point.

It’s worth noting that the Min Stack approach introduces additional space complexity due to the requirement of an extra stack. However, the trade-off is acceptable considering the constant-time retrieval of the minimum element.

The Min Stack approach provides an effective solution for obtaining the minimum element from a stack. By maintaining a separate stack to track the minimums, we can efficiently retrieve the minimum element without compromising the fundamental properties of a stack data structure.

Frequently Asked Questions

Q1. Why is it necessary to use an additional stack for retrieving the minimum element?
Ans. The additional stack, known as the min stack, is used to keep track of the minimum element at each point in the main stack. It ensures constant-time retrieval of the minimum element without having to traverse the entire stack every time. This approach improves efficiency and maintains the LIFO property of the stack.

Q2. What is the time complexity of retrieving the minimum element from the stack using the Min Stack approach?
Ans. The time complexity to retrieve the minimum element using the Min Stack approach is constant, O(1). Since the minimum element is always stored at the top of the min stack, accessing it does not depend on the size of the main stack.

Q3. Does using the Min Stack approach increase the space complexity?
Ans. Yes, using the Min Stack approach increases the space complexity. In addition to the main stack, an extra stack (the min stack) is required to store the minimum elements. However, the space complexity remains proportional to the number of elements in the stack.

Q4. How does the Min Stack approach handle scenarios when the minimum element is popped from the main stack?
Ans. When the minimum element is popped from the main stack, the Min Stack approach ensures consistency by also popping the corresponding minimum element from the min stack. This guarantees that the top of the min stack always represents the minimum element present in the main stack at any given time.

Q5. Can the Min Stack approach be used with any type of stack implementation?
Ans. Yes, the Min Stack approach can be used with any type of stack implementation, whether it’s implemented using an array or a linked list. The key idea is to maintain a separate stack for tracking the minimum elements alongside the main stack.