Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the `MinStack`

class:

`MinStack()`

initializes the stack object.`void push(int val)`

pushes the element`val`

onto the stack.`void pop()`

removes the element on the top of the stack.`int top()`

gets the top element of the stack.`int getMin()`

retrieves the minimum element in the stack.

You must implement a solution with `O(1)`

time complexity for each function.

**Example 1:**

Input

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-2],[0],[-3],[],[],[],[]]Output

[null,null,null,null,-3,null,0,-2]Explanation

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); // return -3

minStack.pop();

minStack.top(); // return 0

minStack.getMin(); // return -2

**Constraints:**

`-231 <= val <= 231 - 1`

- Methods
`pop`

,`top`

and`getMin`

operations will always be called on**non-empty**stacks. - At most
`3 * 104`

calls will be made to`push`

,`pop`

,`top`

, and`getMin`

.

**Idea:**

** Stack** by default supports push(), pop(), top() in O(1) time complexity. But getting the minimum value in O(1) is not default operation of stack data structure.

Lets take the example *[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”][[],[-2],[0],[-3],[],[],[],[]]*

Here after 3 push() operations, how can we get the minimum value from the stack? Naïve way would be look at every single element of the stack to get the minimum which is O(N) operation.

[-2] whats the minimum at this point? -2

[-2,0] ==> min value : 0

[-2,0,-3] ==> min value = -3

How about keeping a single variable to keep track of the minimum value? No it wont work why?

Because for example if you pop() from [-2,0,-3] , that would be [-2,0] and correct answer of new *getMin()* should be at this point: -2. How can we keep the min value at every element?

So what we need is two stacks : (1) ** Stack** for keeping track of elements pushed into the stack (2)

**to store “minimum so far” for each element added to the stack.**

*MinStack*