Back to DSA

Min Stack

medium
Acceptance: 48%
StackDesign

Build a special stack data structure that provides push, pop, and top operations along with the ability to fetch the smallest element currently stored, all executing in constant time. Your MinStack class must expose four methods: push(val) to add a value, pop() to remove the topmost value, top() to inspect the topmost value, and getMin() to return the current minimum across the stack.

Examples

Example 1:
Input:MinStack(), push(5), push(3), push(7), getMin(), pop(), top(), getMin()
Output:[null,null,null,null,3,null,3,3]

Hints

Related Problems

Valid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element IeasyAsteroid Collisionmedium
00:00
import java.util.*;

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

    public void push(int val) {
        stack.push(val);
        minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    }

    public void pop() { stack.pop(); minStack.pop(); }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}
Time complexityO(1)
Space complexityO(n)