You need to modify the design of the stack data structure such that it supports push(), pop(), top() and getMin() operations in constant time( O(1) ).

Problem Note:

• top() gets the top element
• getMin() returns the minimum element in the stack
• push(elem) pushes an element elem in the stack
• pop() removes the top element
• It is guaranteed that input is consistent, i.e., only push() will be called if the stack is supposed to be empty
• Kudos if you solve it using constant space!
• The input provided in this case would be a series of function calls to push(), pop(), top() and getMin()

Example 1

Input:
st = minStack()
st.push(4)
st.push(2)
st.top()      ---> returns 2
st.getMin()   ---> returns 2
st.pop()
st.push(6)
st.getMin()   ---> returns 4

Example 2

Input:
st = minStack()
st.push(-1)
st.push(5)
st.top()       ---> returns 5
st.push(-4)
st.getMin()    ---> returns -4
st.pop()
st.pop()
st.getMin()    ---> returns -1