Stack with min operation in O(1)

Stack with push, pop and min,  all in O(1)

 

Problem

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element so far? Push, pop and min should all operate in O(1) time.

Trivia

This is a pretty standard question now. The question has been asked in many interviews in past and will be asked in many interviews in future.

Approach

There can be many ways to approach this problem:
1) One way is to introduce another variable min in data structure 'Node' which keep tracks of min element so far in the stack.

So the new data structure for stack would look something like:
struct Stack_Node {
   int val;
   int min;
   struct Node *next;
}  Node;

Now when you push the element into stack, its local min variable is calculated and updated.
new->min = Minimum(value, top->min);
And while doing the pop operation, the min is already up to date in stack so far. So one can simply delete the top node.

There is just one problem with this approach - if it is a large stack, we will waste a lot of space keeping track of min element. So if space isn't the issue, like it isn't now a days :), this method is perfectly fine. Otherwise we can do better too.

2) The other way to solve a problem is using additional stack which keep tracks of min so far.

So the new push and pop operations for stack would be like:
stack<int> s2;
push {
    if (value <= s2.top())  s2.push(value)
    s1.push(value)
}
pop {
    value = s1.pop()
    if(value=s2.top()) s2.pop()
}
min {
    if(!s2.isEmpty()) s2.top()
}

Time Complexity

Push - O(1)
Pop - O(1)
Min - O(1)


There is a similar question in which you have to design a stack which, in addition to push and pop, also has a function max which returns the maximum element so far.