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 nonempty 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).