Very Easy C++ Sol. Using 1 Stack All Operations O(1)


#1

stack s;

MinStack::MinStack() {
while(!s.empty())
s.pop();
}

void MinStack::push(int x) {
if(s.empty())
{
s.push(x);
s.push(x);
}
else
{
int y =s.top();
s.push(x);
if(y<x)
s.push(y);
else
s.push(x);
}
}

void MinStack::pop() {
if(!s.empty())
{
s.pop();
s.pop();
}
}

int MinStack::top() {
if(s.empty())
return -1;
else
{
int x=s.top();
s.pop();
int y=s.top();
s.push(x);
return y;
}
}

int MinStack::getMin() {
if(s.empty())
return -1;
else
return s.top();
}


#2

This is so awesome!!!


#3

It uses same memory as 2 stack


#4

This solution is wrong.
check for the following test case -
push(3)
push(2)
push(1)
push(4)
push(5)
now top will be 5 in normal stack and 1 in minimum stack.
do pop() now
as per ur function, 5 and 1will be removed,
making 4 as top() of both stacks which is wrong.
please refer to https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/


#5

@chaitanya-kvk , kid you are wrong try again , solution is absolutely right
you can run it see , you have interpret it correctly! , dry run again


#6

Solution is right all operations in O(1)!


#7

@chaitanya-kvk and here only 1 stack is used , you are mixing 2 solutions …
check again Sol. is right !!


#8

got it understood the code.Thank you.


#11

Bro ,i can not understand why you are doing operation two times example you are pushing x two times…
please help me how to come with this intution??


#12

First push is store the normal element in array and second push is store min element till there so min element is retrieved in O(1) complexity.


#13

@msbobby87
How are you defining a stack as “stack s”?
In my case its not compiling denoting a class error.
But, it accepts the solution when I use “stack s”.


#15

@soumya-patra, It’s stack(int) s triangular braces are not uploaded by website…


#17

please explain , how the pop() function works. why have you popped twice ???


#18

I am trying to keep the min element on the top always , so when we need to pop the actual element, it is the second topmost element on the stack. therefore 2 times pop.
1 for min element
2 for actual element to be poped


#19

Amazing solution ! Thanks a lot


#20

@msbobby87 what if we have to find min after poping an integer


#22

bro why you haven’t use template while defining stack?
you have used
stack s;
but I cant use it. I have to write like this.
stack s;

I have seen many codes where they have written like you without . how you do that?


#23

you got the answer in your question i guess , :smile:


#24

Ha ha . We cant write ‘<’ and ‘>’


#25

No bro you are taking O(n) extra space but good thinking. Please try this with O(1) space and O(1) time.
``stack s;
int m;
MinStack::MinStack() {
while(!s.empty())
{
s.pop();
}
m = -1;
}

void MinStack::push(int x) {
if(s.empty())
{
s.push(x);
m = x;
}
else
{
if(x>=m)
{
s.push(x);
}
else
{
s.push(2*x-m);
m = x;
}
}
}

void MinStack::pop() {
if(!s.empty())
{
if(s.top()>m)
{
s.pop();
if(s.empty())
m=-1;
}
else
{
m = 2*m-s.top();
s.pop();
if(s.empty())
m=-1;
}
}
}

int MinStack::top() {
if(s.empty())
{
return -1;
}
else
{
if(s.top()>m)
return s.top();
else
return m;
}
}

int MinStack::getMin() {
return m;
}

`