Min Stack

Problem

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

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.

Solution

class MinStack {

    Stack<Integer> stack;
    int min;

    public MinStack() {
        this.stack = new Stack<>();
        this.min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        if (x <= min) { //Must be <= here
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        if (stack.pop() == min) min = stack.pop();
    }

    public int getMin() {
        return min;
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

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

Analysis

In this design, we only use one stack and min
The idea is that every time when min is gonna updated in push() method,
we push the original min and then push the new element
Similarly, we need to pop twice if stack.pop() == min and update min