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