Min Stack | Leetcode

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.

---

Solution: Maintain two stacks internally. One is to hold all the elements. The other, minStack, is to only hold the current minimum elements. The current minimum element is always the top element of the minStack.

class MinStack {
    private LinkedList stack = new LinkedList<>();
    private LinkedList minStack = new LinkedList<>();
    
    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        int x = stack.pop();
        if (x == minStack.peek()) {
            minStack.pop();
        }
    }

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

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