CareerCup

i think we can optimize the size of minstack i.e. dont need to push into minstack for every push into stack1

void push(int x)
{
stack1.push(x);
if (x <= minStack.top())
minStack.push(x);
}

int pop()
{
int x=stack1.top();
stack1.pop();
if (x == minStack.top())
minStack.pop();

return x;
}

We have to maintain a parallel stack & maintain running min .

void push(int x)
{
stack1.push(x);
minStack.push(min( x,minStack.top() ) );
}

int pop()
{
int x=stack1.top();
stack1.pop();
minStack.pop();

return x;
}

int min()
{
return minStack.top();
}

i think we can optimize the size of minstack i.e. dont need to push into minstack for every push into stack1

void push(int x)
{
stack1.push(x);
if (x <= minStack.top())
minStack.push(x);
}

int pop()
{
int x=stack1.top();
stack1.pop();
if (x == minStack.top())
minStack.pop();

return x;
}

what is the initial value in minstack..

what is the initial value in minstack..

always keep the min element as TOS.

Hence, minStack=pop();

maintain an invariant.. minimum element till current record
here the element pushed will look like
struct node
{
int data;
int minSoFar;
};

push 10
{10,10}
push 4
{4,4}
push 6
{6,4}

so on.,All we need to do is retireve min element and not modify the current data structure