Stack: Push Pop Min in O(1)

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

Approach 1:

class Node {
Integer data;
Integer min;
}

push(4)
stack: (data:4|min:4) -> null;

push(1)
we compare top min ie 4 with value (1) and we have min so far as 1; Now our stack looks like:
stack: (data:1|min:1) -> (data:4|min:4) -> null;

push(5)
stack: (data:5|min:1) -> (data:1|min:1) -> (data:4|min:4) -> null;

Top give us 5
min gives: 1

With above approach we need additional space of size (n) where n is the size of the stack.

Approach 2:
1. We will have one normal stack S1 which supports usual operations push, pop, and peek.
2. Lets declate another stack called minStack where we will keep the min elements seen so far.

Lets trace now:
push(5)
S1: (5) -> null;
minStack: (5) -> null;

push(4)
S1: (4) -> (5) -> null;
minStack: (4) -> (5) -> null;

push(2)
S1: (2) -> (4) -> (5) -> null;
minStack: (2) -> (4) -> (5) -> null;

push(7)
S1: (7) -> (2) -> (4) -> (5) -> null;
// no change in min stack as 2 is still the min element so far.
minStack: (2) -> (4) -> (5) -> null;

push(9)
S1: (9) -> (7) -> (2) -> (4) -> (5) -> null;
// no change in min stack as 2 is still the min element so far.
minStack: (2) -> (4) -> (5) -> null;

element (2) from the minStack will only be popped out when it's popped from S1.

This approach also has additional space requirement and in worst case it will be of size (n) if all the data is unique and sorted in decreasing order.

Input/Output:

TOP: 9
null -> 4 -> 1 -> 5 -> 7 -> 9
TOP: 1
null -> 4 -> 1