Min Stack — Practice

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

A second, parallel stack tracking the current minimum at each depth is the standard approach — push a new min value (or the same one) alongside every regular push.

Hint 2

The two stacks must always stay in sync — every push/pop on the main stack needs a matching push/pop on the min-stack, even when the value being pushed isn't a new minimum.

Hint 3

A more space-efficient (but trickier) alternative stores only the DIFFERENCE between each value and the min at push time, reconstructing the previous min from that delta on pop.

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(); }
}

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