Get minimum element from stack

Concepts Used:

Stack

Difficulty Level:

Easy.

Problem Statement :

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

Solving Approach:

STACK DATA STRUCTURE

A stack is an Abstract Data Type (ADT), commonly used in most programming languages that can be learnt from best online programming courses. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc.

Stack is LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing.

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.

Solutions:

#include <stdio.h>
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 <bits/stdc++.h>
using namespace std;
stack<int> 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<<Top()<<endl;
    else if(k==4)
        cout<<minimum()<<endl;       
    }
return 0;
}
import java.util.*;
class solution{
   static int minEle;
   static Stack <Integer> 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());     
       }
       }
}

Previous post Beach House
Next post Remove all adjacent duplicates

Leave a Reply

Your email address will not be published. Required fields are marked *