MediumStacks & Queues

Min Stack

stackdesign

Problem

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

Implement the MinStack class:

push(val) — pushes the element val onto the stack
pop() — removes the element on the top
top() — gets the top element
getMin() — retrieves the minimum element in the stack

Examples

Example 1

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Output: -3, 0, -2

Constraints

•-2^31 <= val <= 2^31 - 1
•All operations are valid.

Hints

Hint 1

Use a second stack to track the current minimum at each level.

Solutions

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

    public void push(int val) {
        stack.push(val);
        // Push the new minimum — smaller of val or current min
        int newMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
        minStack.push(newMin);
    }

    public void pop() {
        stack.pop();
        minStack.pop(); // both stacks stay in sync
    }

    public int top()    { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

Java

Time: O(1) all operations · Space: O(n)