Introduction
In this blog, discuss the problem of defining a stack that supports getMin() in O(1) time and O(1) extra space. For this, we have discussed 2 different approaches:
- Naive approach: Here, we maintain an auxiliary stack for storing minimum elements at that instant.
- Optimised Approach: Here, we haven’t used any auxiliary stack. Rather, we have altered the insert operation in a stack.
Stack: A stack is one of a linear data structure where operations are carried out in a specific order. The sequence might be LIFO (Last In First Out) or FILO (First In Last Out) (First In Last Out).
There are several real world examples of stack. Consider a canteen, where the plates are kept on top of each other. The topmost plate is the first to be removed, whereas bottomost plate is the last to be removed. As a result, we see that the stack follows the LIFO (Last In First Out)/FILO (First In Last Out) sequence.
Problem Statement
The problem above states that we have to define a stack that supports getMin() in O(1) time and O(1) extra space.
Sample Example
Consider the below example:
Let us consider the stack containing elements: 3, 2, 6, 5, 4 as shown below:
3 --> top
2
6
5
4
When getMin() gets invoked, it
returns 2, which is the current
minimum of the stack.
If we pop 2 elements of the stack,
Below is the configuration.
6 --> top
5
4
Now, we again getMin() is invoked, it
Returns 4 as the minimum.Naive Approach
The naive approach here includes having two stacks, where one stack stores the actual elements and the other auxiliary stack stores the minimum elements at that point. Now, to implement this, we have to accordingly perform the push() and pop() elements.
Below is the solution:
Push()
- We insert element x into stack one.
- While inserting element x, we compare this element with the top of the auxiliary stack.
- If stack two is empty, we push the element in stack two.
- If x < top of stack two, it means that this is the new current minimum. Therefore we store x in stack two.
- If x > top of stack two, we store the previous top of stack two.
Pop()
- We pop the element from stack one.
- We pop the element from stack two.
getMin()
- We return the top of stack two.
Pseudocode
class Stack
Stack(size)
int stackone[size]
int stacktwo[size]
int topone equals -1
int toptwo equals -1
Push(x)
stack[topone]=x
topone+=1
stacktwo = minimum(x, stacktwo[toptwo])
toptwo+=1
Pop()
topone-=1
toptwo-=2
GetMin()
return stacktwo[toptwo]
Implementation in C++
#include "bits/stdc++.h"
using namespace std;
//Below is the class for stack;
class Stack{
//Below are the class parameters
public:
int lim;
//This is for stack one
int *stackone;
int top1;
//This is for stack 2;
int *stacktwo;
int top2;
//Here we initialise the stack. Parameterized constructor;
Stack(int size){
lim = size;
stackone = new int[size];
top1 = -1;
stacktwo = new int[size];
top2 = -1;
}
//Push function to insert
void push(int x){
//Checking if stack is full or not;
if (top1 == lim){
cout << "Stack full\n";
}
//Inserting in stack
top1+=1;
stackone[top1]=x;
top2+=1;
//Inserting in stack 2; Before inserting, we check if
//New element is the new minimum. Else we insert last
//Element itself.
stacktwo[top2]=min(stacktwo[top2-1],x);
}
//Pop funcion for removing elements;
void pop(){
if(top1 == -1){
cout<<"Stack Empty\n";
}
top1--;top2--;
}
//Get min functio simply
//Return top of stack 2;
int GetMin(){
if(top1 == -1){
cout<<"Stack Empty\n";
}
return stacktwo[top2];
}
};
void solve()
{
int a[5] = {4,5,6,2,3};
Stack ob(20);
for(auto i: a){
ob.push(i);
}
cout<<"Minimum: ";
cout<<ob.GetMin();
ob.pop();ob.pop();
cout<<"\nNew Miniumum: "<<ob.GetMin();
}
int main()
{
solve();
return 0;
}Implementation in Python
class Stack:
#Initialising a stack;
def __init__(self, size):
self.topone = -1
self.stackone = [0]*size
self.lim = size
self.stacktwo = [0]*size
self.toptwo = -1
# Getting Minimum of stack
def GetMin(self):
if self.topone == -1:
print("Empty Stack")
else:
print("Minimum: {}" .format(self.stacktwo[self.toptwo]))
# Adding an element to stack
def push(self,x):
if self.topone == self.lim:
print("Stack Full")
if self.topone == -1:
self.topone+=1
self.toptwo+=1
self.stackone[self.topone] = x
self.stacktwo[self.toptwo] = x
else:
self.topone+=1
self.toptwo+=1
self.stackone[self.topone] = x
self.stacktwo[self.toptwo] = min(self.stacktwo[self.toptwo-1], x)
# Poping an element from the stack
def pop(self):
if self.topone == -1:
print( "Empty Stack")
else:
self.toptwo-=1;
self.topone-=1;
# Driver program to test above class
stack = Stack(100)
a = [4,5,6,3,2]
for i in a:
stack.push(i)
stack.GetMin()
stack.pop()
stack.pop()
stack.GetMin()
Complexity Analysis
Time complexity: Below is the time complexity of all operations:
- Push: O(1)
- Pop(): O(1)
- Getmin: O(1)
Explanation: For the above approach, the time complexity of all the three push pop and getmin is O(1). This is so because we either insert an element in the stack or we delete the element by decrementing the top1/top2 variable.
Space complexity: O(n)
Explanation: As in the above approach, we had created a new auxiliary stack for storing the current minimum element. Therefore the worst-case time complexity is O(n).
Read More - Time Complexity of Sorting Algorithms
569+ registered 
