Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Min Stack

Easy

0/40

Contributed by

97 upvotes

Asked in companies

Problem statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

1. Push(num): Push the given number in the stack.
2. Pop: Remove and return the top element from the stack if present, else return -1.
3. Top: return the top element of the stack if present, else return -1.
4. getMin: Returns minimum element of the stack if present, else return -1.

For Example:

For the following input: 
1
5
1 1
1 2
4
2
3

For the first two operations, we will just insert 1 and then 2 into the stack which was empty earlier. So now the stack is => [2,1]
In the third operation, we need to return the minimum element of the stack, i.e., 1. So now the stack is => [2,1]
For the fourth operation, we need to pop the topmost element of the stack, i.e., 2. Now the stack is => [1]
In the fifth operation, we return the top element of the stack, i.e. 1 as it has one element. Now the stack is => [1]

So, the final output will be: 
1 2 1

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single integer ‘N’, denoting the no. of the operations.

The next ‘N’ lines of each test case contain either of the operations in the following format: - 
Push -> two space-separated integers, 1 and ‘X’ like “1 X”. We need to push ‘X’ on top of the stack.
Pop -> single integer 2. We need to remove the topmost element from the stack.
Top -> single integer 3. We need to return the topmost element from the stack.
getMin -> single integer 4, We need to return the minimum element of the stack if present and 0 otherwise.

Output Format:

For each test case, print the results of the operations performed on the stack separated by spaces.

Print output of each test case in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints -

1 ≤ T ≤ 1000
1 ≤ N ≤ 100000
ΣN ≤ 200000
1 ≤ X ≤ (10^9)

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

1 2 1
13 -1 -1

Explanation For Sample Input 1 :

For First Case - Similar to the example explained above. 

For Second Case - 
For the first operation, we will just insert 13 into the stack which was empty earlier. So now the stack is => [13]
In the second operation, we need to remove the topmost element 13 and return it for printing. Now the stack is => [] (empty)
For the third operation, we need to return the topmost element of the stack. As the stack is empty we will return -1. Now the stack is => [] (empty)
 In the fourth operation, we return the minimum element of the stack if it is not empty, i.e. -1 as it has no elements. Now the stack is => [] (empty)

Sample Input 2 :

Sample Output 2 :

-1 -1 4
45 19 45 19

Hint 1

Can we do some additional bookkeeping that helps us in getting a minimum of the stack?

Approaches (1)

Approach 1

Naive Simulation

The basic idea is to store two stacks. One for regular stack and one for storing prefix minimums of our regular stack. We store values at which our minimum changes so that those values are stored and can be accessed later when we pop elements on top of it. We just return the top value of Min stack whenever we are asked getMin(). The implementation details are depicted in the following algorithm.

Algorithm:

push(num)

Function arguments - a no. num which is to be inserted on top of the stack.

Push num into the regular stack
If Min stack is empty OR num ≤ top of Min stack
- Push num into Min stack

pop()

Returns data that is popped or -1 if the stack was already empty

If Min stack is not empty AND top of Min stack = top of the regular stack
- Pop top element of Min stack
ret = -1
If the regular stack is not empty
- ret = Top of the regular stack
- Pop top of the regular stack
Return ret

top()

Returns the value of node on top of the stack or -1 if the stack was already empty

ret = -1
If the regular stack is not empty
- ret = Top of the regular stack
Return ret

getMin()

Returns the minimum element of the stack if it exists and -1 otherwise.

ret = -1
If the min stack is not empty
- ret = top of Min stack
Return ret

Time Complexity

O(N) where N is the no. of operations performed.

All of our operations are doing some constant no. of operations and taking O(1). For each of the operations, we will take O(1) time. Hence the final time complexity will be O(N) for N operations.

Space Complexity

O(N) where N is the no. of operations performed.

We have to store two stacks: “Stack” and “Min”. The size of each of the stacks can be at most N. So each stack will take O(N) space. So total space required = O(N)+O(N) = O(N).

(75% EXP penalty)

(100% EXP penalty)

Min Stack

shivam yadav

Interview problems

Easy C++ solution

#include <bits/stdc++.h>

// Implement class for minStack.

class minStack

{

// Write your code here.

stack<pair<int,int>>st;

public:

// Constructor

minStack()

{

// Write your code here.

}

// Function to add another element equal to num at the top of stack.

void push(int val)

{

// Write your code here

if(st.empty()) st.push({val,val});

else st.push({val, min(val, st.top().second)});

}

// Function to remove the top element of the stack.

int pop()

{

// Write your code here.

if(st.empty()) return -1;

int x = st.top().first;

st.pop();

return x;

}

// Function to return the top element of stack if it is present. Otherwise return -1.

int top()

{

// Write your code here.

if(st.empty()) return -1;

return st.top().first;

}

// Function to return minimum element of stack if it is present. Otherwise return -1.

int getMin()

{

// Write your code here.

if(st.empty()) return -1;

return st.top().second;

}

};

47 views

0 replies

1 upvote

Varun Bhandari M

Interview problems

minStack

import java.util.* ;

import java.io.*;

public class Solution {

static class MinStack {

Stack<Long>st=new Stack<>();

Long min;

// Constructor

MinStack() {

// Write your code here.

min=Long.MAX_VALUE;

}

// Function to add another element equal to num at the top of stack.

void push(int value) {

// Write your code here.

Long val=Long.valueOf(value);

if(st.isEmpty()){

st.push(val);

min=val;

}else{

if(val<min){

st.push(2*val-min);

min=val;

}else{

st.push(val);

}

// Function to remove the top element of the stack.

int pop() {

// Write your code here.

if(st.isEmpty())return -1;

Long val=st.pop();

if(val<min){

Long prevMin = min;

min=2 * min-val;

return prevMin.intValue();

}

return val.intValue();

}

// Function to return the top element of stack if it is present. Otherwise

// return -1.

int top() {

// Write your code here.

if (st.isEmpty()) return -1;

Long val=st.peek();

if(val<min){

return min.intValue();

}

return val.intValue();

}

// Function to return minimum element of stack if it is present. Otherwise

// return -1.

int getMin() {

// Write your code here.

if (st.isEmpty()) return -1;

return min.intValue();

}

39 views

0 replies

0 upvotes

Govinda

Interview problems

EASIEST AND FASTEST C++ SOLUTION

#include <bits/stdc++.h>

// Implement class for minStack.

class minStack

{

stack<int> st;

int mini;

public:

// Constructor

minStack()

{

mini = INT_MAX;

}

// Function to add another element equal to num at the top of stack.

void push(int num)

{

if(st.empty()){

st.push(num);

mini = num;

}

else{

if(num >= mini){

st.push(num);

}

else{

int val = (2*num)-mini;

st.push(val);

mini = num;

}

// Function to remove the top element of the stack.

int pop()

{

if(st.empty())

return -1;

else{

int curr = st.top();

st.pop();

if(curr < mini){

int val = mini;

mini = (2*mini) - curr;

return val;

}

else{

return curr;

}

// Function to return the top element of stack if it is present. Otherwise return -1.

int top()

{

if(st.empty())

return -1;

else if(st.top() >= mini)

return st.top();

else{

return mini;

}

// Function to return minimum element of stack if it is present. Otherwise return -1.

int getMin()

{

if(st.empty())

return -1;

else

return mini;

}

};

485 views

0 replies

1 upvote

Manish Kumar

Interview problems

java solution using stack

import java.util.Stack;

public class Solution {

static class MinStack {

Stack<Long> stack;

long min;

// Constructor

MinStack() {

stack = new Stack<>();

min = Long.MAX_VALUE;

}

// Function to add another element equal to num at the top of stack.

void push(int num) {

long val = (long) num;

if (stack.isEmpty()) {

stack.push(val);

min = val;

} else {

if (val < min) {

stack.push(2 * val - min);

min = val;

} else {

stack.push(val);

}

// Function to remove the top element of the stack.

int pop() {

if (stack.isEmpty()) return -1;

long val = stack.pop();

if (val < min) {

long prevMin = min;

min = 2 * min - val;

return (int) prevMin;

}

return (int) val;

}

// Function to return the top element of stack if it is present. Otherwise

// return -1.

int top() {

if (stack.isEmpty()) return -1;

long val = stack.peek();

if (val < min) {

return (int) min;

}

return (int) val;

}

// Function to return minimum element of stack if it is present. Otherwise

// return -1.

int getMin() {

if (stack.isEmpty()) return -1;

return (int) min;

}

153 views

0 replies

0 upvotes

Rajat Pandey

Interview problems

Java Solution | getMin() in O(1) Without Using Extra Space

import java.util.* ;
import java.io.*; 
import java.util.Stack;

public class Solution {
    static class Pair {
        int value;
        int min;

        public Pair(int value, int min) {
            this.value = value;
            this.min = min;
        }
    }

   static class MinStack {
        Stack<Pair> stack;

        public MinStack() {
            stack = new Stack<>();
        }

        public void push(int num) {
            int min = stack.isEmpty() ? num : Math.min(num, stack.peek().min);
            stack.push(new Pair(num, min));
        }

        public int pop() {
            if (stack.isEmpty()) return -1;
            return stack.pop().value;
        }

        public int top() {
            if (stack.isEmpty()) return -1;
            return stack.peek().value;
        }

        public int getMin() {
            if (stack.isEmpty()) return -1;
            return stack.peek().min;
        }
    }
}

programming

java

119 views

0 replies

0 upvotes

Dayharika kunam

Interview problems

best optimal approach

#include <bits/stdc++.h>

// Implement class for minStack.

class minStack

{

// Write your code here.

int *arr;

int size;

int ttop;

int min;

public:

// Constructor

minStack()

{

// Write your code here.

size=100001;

arr=new int[size];

ttop=-1;

min=INT_MAX;

}

// Function to add another element equal to num at the top of stack.

void push(int num)

{

// Write your code here.

if(ttop==size-1){

cout<<"stack is full"<<endl;

}

ttop++;

if(ttop==0){

min=num;

arr[ttop]=num;

}else{

if(num<min){

arr[ttop]=2*num-min;

min=num;

}else{

arr[ttop]=num;

}

// Function to remove the top element of the stack.

int pop()

{

// Write your code here.

if(ttop==-1){

return -1;

}else{

int popped=arr[ttop];

if(arr[ttop]<min){

popped=min;

min=2*min-arr[ttop];

}

ttop--;

return popped;

}

// Function to return the top element of stack if it is present. Otherwise return -1.

int top()

{

// Write your code here.

if(ttop==-1){

return -1;

}else{

if(arr[ttop]<min){

return min;

}

return arr[ttop];

}

// Function to return minimum element of stack if it is present. Otherwise return -1.

int getMin()

{

// Write your code here.

if(ttop==-1){

return -1;

}

return min;

}

};

376 views

0 replies

0 upvotes

Interview problems

C++ solution, not optimal but alternative approach.

works in O(n) instead of the tradational O(1) minstack approach. Check out if you're looking for alternative approaches :)

#include <bits/stdc++.h>

using namespace std;

class minStack

{

public:

stack<int>st,st2;

int min=INT_MAX;

minStack()

{

}

// Function to add another element equal to num at the top of stack.

void push(int num)

{

st.push(num);

if(num<min)

min=num;

}

int pop()

{if(st.empty())

return -1;

int x=st.top();

st.pop();

if (x == min) {

// If the popped element was the minimum, update min

min = INT_MAX;

// Traverse st to find the new minimum

while (!st.empty()) {

if (st.top() < min)

min = st.top();

st2.push(st.top());

st.pop();

}

// Restore st

while (!st2.empty()) {

st.push(st2.top());

st2.pop();

}

return x;

}

// Function to return the top element of stack if it is present. Otherwise return -1.

int top()

{if(st.empty())

return -1;

return st.top();}

int getMin()

{if(st.empty())

return -1;

return min;

}

};

182 views

0 replies

2 upvotes

Ritik Gajjalwar

Interview problems

Easy C++ Solution by using vector

#include <bits/stdc++.h>

// Implement class for minStack.

class minStack

{

public:

vector<int>st;

int cnt;

minStack()

{

cnt = 0;

}

// Function to add another element equal to num at the top of stack.

void push(int num)

{

st.push_back(num);

cnt++;

}

// Function to remove the top element of the stack.

int pop()

{

if(cnt != 0)

{

int temp = st[cnt-1];

st.pop_back();

cnt--;

return temp;

}

else{

return -1;

}

// Function to return the top element of stack if it is present. Otherwise return -1.

int top()

{

if(cnt != 0)

{

return st[cnt-1];

}

else{

return -1;

}

// Function to return minimum element of stack if it is present. Otherwise return -1.

int getMin()

{

int min = INT_MAX;

if(cnt != 0)

{

for(int i=0; i<cnt; i++)

{

if(st[i] < min)

{

min = st[i];

}

return min;

}

else{

return -1;

}

};

261 views

0 replies

1 upvote

Satvik Madan

Interview problems

EASY C++ SOLUTION ....... STRIVER SOLUTION

#include <bits/stdc++.h> 
// Implement class for minStack.
class minStack
{
	
	
	public:
		
		stack<pair<int,int>>s;

		minStack() 
		{ 
			
		}
		
		// Function to add another element equal to num at the top of stack.
		void push(int num)
		{
			int mini;
			if(s.empty()) mini = num;
			else{
				mini = min(num,s.top().second);
			}
			s.push({num,mini});
		}
		
		// Function to remove the top element of the stack.
		int pop()
		{
			if(s.empty()) return -1;
			else{
			   int temp = s.top().first;
			   s.pop();
			   return temp;
			}
		}
		
		// Function to return the top element of stack if it is present. Otherwise return -1.
		int top()
		{
			if(s.empty()) return -1;
			else{
			   int temp = s.top().first;
			   
			   return temp;
			}
		}
		
		// Function to return minimum element of stack if it is present. Otherwise return -1.
		int getMin()
		{
			if(s.empty()) return -1;
			else{
				return s.top().second;
			}
		}
};

305 views

0 replies

1 upvote

Gaurav Kumar

Interview problems

Min Stack | C++ O(1) Easy solution

#include <bits/stdc++.h> 
// Implement class for minStack.
class minStack
{
	
	
	public:
		
		stack<pair<int,int>>s;

		minStack() 
		{ 
			
		}
		
		// Function to add another element equal to num at the top of stack.
		void push(int num)
		{
			int mini;
			if(s.empty()) mini = num;
			else{
				mini = min(num,s.top().second);
			}
			s.push({num,mini});
		}
		
		// Function to remove the top element of the stack.
		int pop()
		{
			if(s.empty()) return -1;
			else{
			   int temp = s.top().first;
			   s.pop();
			   return temp;
			}
		}
		
		// Function to return the top element of stack if it is present. Otherwise return -1.
		int top()
		{
			if(s.empty()) return -1;
			else{
			   int temp = s.top().first;
			   
			   return temp;
			}
		}
		
		// Function to return minimum element of stack if it is present. Otherwise return -1.
		int getMin()
		{
			if(s.empty()) return -1;
			else{
				return s.top().second;
			}
		}
};

238 views

0 replies

1 upvote

Console