# Min Stack

Companies:

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.

### 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).
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.