'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Jun 30, 2023

Stack that supports getMin() in O(1) time and O(1) extra space

Author Akshit Mehra
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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:

  1. Naive approach: Here, we maintain an auxiliary stack for storing minimum elements at that instant.
  2. 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()

  1. We insert element x into stack one.
  2. While inserting element x, we compare this element with the top of the auxiliary stack.
  3. If stack two is empty, we push the element in stack two.
  4. If x < top of stack two, it means that this is the new current minimum. Therefore we store x in stack two.
  5. If x > top of stack two, we store the previous top of stack two.

 

Pop()

  1. We pop the element from stack one.
  2. We pop the element from stack two.

 

getMin()

  1. 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:

  1. Push: O(1)
  2. Pop(): O(1)
  3. 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimised Approach

In the optimised approach, rather than maintaining an auxiliary stack, we try to change the way the stack inserts the elements in it. Here, rather than storing current element x directly, we store 2*x - MinElement in the stack. This helps us get previous elements using current min and stored values. Below is the solution:

Push()

  1. If the stack is empty, add x to it and set minEle equal to x.
  2. Compare x with minEle if the stack isn't empty. There are two scenarios:
  3. Insert x if x is greater than or equal to minEle.
  4. If x is less than minEle, make minEle equal to x by inserting (2*x – minEle) onto the stack.

 

Pop()

Remove the top element. Let y be the eliminated element. There are two scenarios:

  1. If y is more than or equal to minEle, minEle remains the stack's lowest member.
  2. If y is smaller than minEle, the minimal element is now (2*minEle – y); therefore, (minEle = 2*minEle – y) should be updated. This is where we get the prior minimum and its value from the current minimum. 

 

getMin():

  1. Return the value of minEle

Pseudocode

class Stack
	Stack(size)
		int stack[size]
		int top equals -1
		Int minEle = -1

	Push(x)
		top+=1
		if x >= minEle:
			stack[top] = x
		else:
			stack[top] = 2x - minEle
			minEle = x

	Pop()
		if x >= minEle:
			top-=1
		else:
			minEle = 2*minEle - stack[top]
			top-=1 
	GetMin()
		return minEle

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 *stack;
    int top;
    int minEle;

    //Here we initialise the stack. Parameterized constructor;
    Stack(int size){
        lim = size;
        stack = new int[size];
        top = -1;
    }


    //Push function to insert
    void push(int x){

        //Checking if stack is full or not;
        if (top == lim){
            cout << "Stack full\n";
        }
       
       //If stack Empty
        if (top == -1){
            top+=1;
            minEle = x;
            stack[top] = x;
        }

        else{
            //If x is greater than minimum Element, we simply push
            //x
            if(x >= minEle){
                top+=1;
                stack[top] = x;
            }else{
                top+=1;

                //Storing 2*x - minEle
                stack[top]=2*x - minEle;
                //Updating the value minElement;
                minEle = x;
            }
        }

    }

    //Pop function for removing elements;
    void pop(){

        //If stack is empty;
        if(top == -1){
            cout<<"Stack Empty\n";
        }

        //If stack top is greater than minElemnt
        if(stack[top] >= minEle){
            top--;
        }else{

            //Updating the value of minEle to previous
            //Minimum
            minEle = 2*minEle-stack[top];
            top-=1;
        }
    }

    //Get min function simply
    int GetMin(){
        if(top == -1){
            cout<<"Stack Empty\n";
        }

        //Returning minMum element;
        return minEle;
    }
};
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.top = -1
		self.stack = [0]*size
		self.lim = size
		self.min_ = -1

	# Getting Minimum of stack
	def GetMin(self):
		if self.top  == -1:
			print("Empty Stack")
		else:
			print("Minimum: {}" .format(self.min_))

# Adding an element to stack
def push(self,x):
    if self.top == self.lim:
        print("Stack Full")
   
    if self.top == -1:
        self.top+=1
        self.stack[self.top] = x
        self.min_ = x
        
    else:
        if (x >= self.min_) :
            self.top+=1
            self.stack[self.top] = x
        else:
            self.top+=1
            self.stack[self.top] = 2*x - self.min_
            self.min_ = x

# Popping an element from the stack
def pop(self):
if self.top == -1:
print( "Empty Stack")
else:
if self.stack[self.top] >= self.min_:
    self.top-=1;
else:
    self.min_ = 2*self.min_ - self.stack[self.top]
    self.top-=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:

  1. Push: O(1)
  2. Pop(): O(1)
  3. Getmin: O(1)

 

Explanation: For the above approach, the time complexity of all the three push pop and getmin in O(1). This is so because we either insert an element in the stack or delete the element by decreasing the top variable.

Space complexity: O(1)

Explanation: As in the above approach, we haven’t used any auxiliary stack for storing minimum. Therefore, the space complexity becomes O(1).

Must Read Stack Operations

Frequently Asked Questions

What is a stack data structure?

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.

How is stack different from queue data structure?

We observe LIFO (Last in, first out) functionality in the stack. But in the queue data structure, we have FIFO (First in, first out) functionality.

What is the time complexity of different stack functions?

The following methods are related with stack: 

  1. empty() – Returns true if the stack is empty – Time Complexity: O(1) 
  2. size()  – Returns the stack size – Time Complexity: O(1) (1)
  3. top()  – Returns a reference to the stack's topmost member  – Complexity of Time: O (1)
  4. push(g) – Pushes the 'g' element to the top of the stack – Complexity of Time: O (1)
  5. pop() – Removes the stack's topmost member – Time Complexity: O (1)

Conclusion

This article discussed the problem of defining a stack that supports getMin() in O(1) time and O(1) extra space. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Recommended Problems:

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

We hope that this blog has helped you increase your knowledge regarding such DSA problems, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

Previous article
Check if a queue can be sorted into another queue using a stack
Next article
How To Sort A Stack Using Recursion?
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass