Design a stack that supports getMin() in O(1) time and O(1) extra space

Design a stack that supports getMin() in O(1) time and O(1) extra space. Thus the special stack data structure must support all the operations of the stack like –

• void push()
• int pop()
• bool isFull()
• bool isEmpty()

in constant time. Add an additional operation getMin() to return the minimum value in special stack in constant time and O(1) extra space.

Example

push(30)
push(20)
push(10)
getMin()
pop()
getMin()

Minimum element : 10
Popped element : 10
Minimum element : 20

push(500)
push(50)
push(5)
getMin()
pop()
getMin()

Minimum element : 5
Popped element : 5
Minimum element : 50

Mathematical/Observed Method for implementing minStack

In this approach we are updating the minimum element as –

In push() function if integer to be pushed is less than the minimum element we are inserting twice of that integer minus minimum element in stack which will always be smaller than the given integer as –

• given integer < minimum element which means given integer – minimum element < 0
• // Adding given integer on both sides
• given integer – minimum element + given integer < 0 + given integer
• 2*given integer – minimum element < given integer
• We can conclude 2*given integer – minimum element < new minimum element

so while popping out this element it will be less than the minimum element therefore we’ll update the minimum element.

Similarly, in pop() function, if current element is less than the minimum element we’ll update it.

Algorithm

1. Initialize a structure newStack and create a function push() in it which accepts an integer as a parameter.
2. Check if the stack is empty, store the integer in a variable min, insert the integer in stack and return.
3. Else if integer is less than min insert 2*x – min in stack and update min as x.
4. Else push the integer in stack.
5. Create the function pop(). Check if stack is empty print “Stack is empty” and return.
6. Else store the element at top of stack in a variable t and pop/remove the top element from stack.
7. Check if t is less than min print min and update min as 2*min – t.
8. Else print t.
9. Create the function getMin() and check if the stack is empty print “Stack is empty”.
10. Else return the minimum element.

Code

C++ Program for minStack

#include <bits/stdc++.h> 
using namespace std; 
  
struct newStack{ 
    stack<int> s; 
    int min; 
  
    void getMin(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
        }
        else{
            cout<<"Minimum element : "<<min<<"\n"; 
        }    
    } 
  
    void pop(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
            return; 
        } 
  
        cout<<"Popped element : "; 
        int t = s.top(); 
        s.pop(); 
  
        if(t<min){ 
            cout<<min<< "\n"; 
            min = 2*min - t; 
        } 
  
        else{
            cout<<t<< "\n";
        }    
    } 
  
    void push(int x){ 
        if(s.empty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x < min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
           s.push(x);
        }   
    } 
}; 
 
int main(){
    newStack s; 
    
    s.push(30);
    s.push(20);
    s.push(10);
    s.getMin();
    s.pop();
    s.getMin();
  
    return 0; 
}

Minimum element : 10
Popped element : 10
Minimum element : 20

Java Program for minStack

import java.util.*; 
  
class newStack{ 
    Stack<Integer> s; 
    Integer min; 
  
    newStack(){ 
        s = new Stack<Integer>(); 
    } 
  
    void getMin(){ 
        if(s.isEmpty()) 
            System.out.println("Stack is empty"); 
  
        else{
            System.out.println("Minimum element : " + min);
        }    
    } 
  
    void pop(){ 
        if (s.isEmpty()){ 
            System.out.println("Stack is empty"); 
            return; 
        } 
  
        System.out.print("Popped element : "); 
        Integer t = s.pop(); 
  
        if(t<min){ 
            System.out.println(min); 
            min = 2*min - t; 
        } 
  
        else{
            System.out.println(t);
        }    
    } 
  
    void push(Integer x){ 
        if(s.isEmpty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x<min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
            s.push(x); 
        }    
    } 
}; 
  
public class Main{ 
    public static void main(String[] args){ 
        newStack s = new newStack(); 
        
        s.push(30);
        s.push(20);
        s.push(10);
        s.getMin();
        s.pop();
        s.getMin();
        
    } 
}

Minimum element : 10
Popped element : 10
Minimum element : 20

Complexity Analysis

Time Complexity

O(1) for each operation, as all operations are being done in constant time.

Space Complexity

O(1) because we are using contant auxiliary space. The space required to store input does not count towards the space complexity of algorithm.