142. Min Stack

getMin has to be O(1), but min(stack) is O(n). The trick: maintain a second stack that, at every moment, has the running minimum at its top. Push and pop in lockstep with the main stack and the top of the mins-stack is always exactly the minimum of the values currently in the main stack.

Why we need a second stack

If we only kept one stack, finding the minimum would require scanning all elements — O(n). We could store "the current min" in a single variable, but then a pop() of the current minimum would force us to recompute by scanning. The mins-stack solves both: it remembers what the minimum would be after a pop, by stashing the historical minimum at every level.

Steps

For each operation:

• push(val):
  1. Append val to stack.
  2. Compute the new running min: m = val if mins is empty, else m = min(val, mins[-1]). Append m to mins.
• pop():
  1. Pop the top of stack.
  2. Pop the top of mins (the running min becomes whatever it was before this push).
• top(): return stack[-1].
• getMin(): return mins[-1].

Walk-through

Why the mins-stack stays correct

By induction: after each push, mins[-1] equals min of all values currently in stack (because we computed it as min(new value, previous min)). After each pop, both stacks shrink in lockstep, so mins[-1] once again equals the min of the remaining values.

Edge cases

• Empty stack: the problem says ops only happen on non-empty stacks for top and getMin, so we don't need to guard.
• Duplicates: push(2); push(2) produces mins = [2, 2]. The min semantics still work — popping one 2 leaves the other on top.
• All identical values: mins is just a copy of stack. Still O(n) extra, but correct.

Complexity

• Time: O(1) per operation — just stack push/pop.
• Space: O(n) — two stacks, each holds up to n items.

import java.util.*;

class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> mins;

    public MinStack() {
        stack = new ArrayDeque<>();
        mins = new ArrayDeque<>();
    }

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

    public void pop() {
        stack.pop();
        mins.pop();
    }

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

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