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

Problem Note:

  • top() gets the top element
  • getMin() returns the minimum element in the stack
  • push(elem) pushes and 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

Input Format:

First line contains N, the total number of queries.

Each of the following N lines has a query of any of the 4 types, type 1(push), type 2(pop), type 3(top), type 4(getMin).

Query for type 1 is of format: 1 v, where v is value

Query for type 2, 3 and 4 just mention the query type number

For example, the input for example 1 will be:

7
1 4
1 2
3
4
2
1 6
4