# Min Stack

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.
Note that all the operations have to be constant time operations.

Questions to ask the interviewer :

```Q: What should getMin() do on empty stack?
A: In this case, return -1.

Q: What should pop do on empty stack?
A: In this case, nothing.

Q: What should top() do on empty stack?
A: In this case, return -1
```
NOTE : If you are using your own declared global variables, make sure to clear them out in the constructor.
Solution:

Time: N/A
Space: O(n)

```class Solution {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> minStack = new ArrayDeque<>();

public void push(int x) {
stack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
} else {
int curMin = minStack.peekFirst();
if (x < curMin) {
minStack.push(x);
} else {
minStack.push(curMin);
}
}
}

public void pop() {
if (stack.isEmpty()) return;
stack.pop();
minStack.pop();
}

public int top() {
if (stack.isEmpty()) return -1;
return stack.peekFirst();
}

public int getMin() {
if (minStack.isEmpty()) return -1;
return minStack.peekFirst();
}
}```

```class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;

/** initialize your data structure here. */
public MinStack() {
stack = new ArrayDeque();
minStack = new ArrayDeque();
}

public void push(int x) {
stack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
} else if (x < minStack.peekFirst()) {
minStack.push(x);
} else {
minStack.push(minStack.peekFirst());
}
}

public void pop() {
stack.pop();
minStack.pop();
}

public int top() {
return stack.peekFirst();
}

public int getMin() {
return minStack.peekFirst();
}
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/```