O(1) time with O(1) extra space! Happy coding!


#1

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;
}


#2

@raunak-rathour Bro when you are using stack then its never O(1) , your sol. is O(N) !!!


#3

I here meant O(1) time to do required operations like peeking minimum element, top(), push() and pop().


#4

How have you declared stack as just “stack s;” ?
I dont understand. I wrote similar code but stacks; gives error for long ass test cases and declaring stack like that just gives compilation error


#5

Dude, this was genius