Min stack — push/pop/min in O(1).

Problem. Design a stack supporting push, pop, top, and getMin — the minimum element currently on the stack — all in O(1).

Brute force — O(n) getMin

Keep a single stack and scan it on every getMin. Push/pop stay O(1), but getMin becomes O(n), which defeats the point. Tracking a single min field also fails: when you pop the current minimum you have no idea what the previous minimum was.

Optimal — O(1) everything, O(n) space

The fix to the "what was the previous min?" problem is to remember the minimum at each level of the stack. Use a second stack that, at every push, records the running minimum. Pop both together and the top of the min-stack is always the current minimum.

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

    public void push(int x) {
        stack.push(x);
        // running min: smaller of x and the previous min
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }

    public void pop() {
        stack.pop();
        mins.pop();          // discard this level's min in lockstep
    }

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

Every operation touches only stack tops, so all four are O(1). Space is O(n) for the auxiliary stack.