design a stack such that getMinimum( ) should be O(1)

This is an interview question.

You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack.

For example:

case #1

5 ← TOP
1
4
6
2

When getMinimum() is called it should return 1, which is the minimum element in the stack.

case #2

stack.pop()
stack.pop()

Note: Both 5 and 1 are popped out of the stack. So after this, the stack looks like

4 ← TOP
6
2

When getMinimum() is called it should return 2 which is the minimum in the stack.

Constraints:

1. getMinimum should return the minimum value in O(1)
2. Space constraint also has to be considered while designing it and if you use extra space, it should be of constant space.