## Min Stack Link

*Companies: Amazon, Netflix, Google, Bloomberg, Microsoft, Adobe, Oracle, Apple.*

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

- push(x) — Push element x onto stack.
- pop() — Removes the element on top of the stack.
- top() — Get the top element.
- getMin() — Retrieve the minimum element in the stack.

#### 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:

Methods `pop`

, `top`

and `getMin`

operations will always be called on non-empty stacks.

### Solution

The solution for this problem is a tricky one. As per the given constraints, we need to solve this problem in a constant time, so basically we can’t do any thing with the iterations here. Our main part to solve this problem in a constant time lies in a solution to find the minimum value in a stack because this is not possible if we simply implement stack and solve this.

To solve this problem we will apply two logics here:

- We will always push the second minimum number on to the stack before we push the upcoming number. This will help us to find the next minimum number in a constant time whenever we pop the top of the stack.
- If the current minimum number is the top of the stack, we will pop twice and change the current minimum number to be the last minimum number we popped.

### Implementation:

### Java

```
class MinStack {
private Stack<Integer> stack;
private int min;
public MinStack() {
stack = new Stack();
min = Integer.MAX_VALUE;
}
public void push(int x) {
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
if (min == stack.pop()) {
min = stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
```

### Complexity Analysis:

**Time Complexity:**O(1).**Space Complexity:**O(n).