155. Min Stack

Intuition

To support constant-time retrieval of the minimum element (getMin()), we need to track the minimum at every stage of the stack. Rather than searching the stack, we store the current minimum alongside each value pushed.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(1)$

Code

class MinStack {
    Stack<int[]> stackWithMin; // Stack storing value and current min
    int currentMin;

    public MinStack() {
        stackWithMin = new Stack<>();
        currentMin = Integer.MAX_VALUE;
    }

    // Pushes a value and current min onto the stack
    public void push(int value) {
        currentMin = Math.min(value, currentMin);
        stackWithMin.push(new int[]{value, currentMin});
    }

    // Pops the top element and updates the current min
    public void pop() {
        stackWithMin.pop();
        currentMin = stackWithMin.isEmpty() ? Integer.MAX_VALUE : stackWithMin.peek()[1];
    }

    // Returns the top value of the stack
    public int top() {
        return stackWithMin.peek()[0];
    }

    // Returns the current minimum value in the stack
    public int getMin() {
        return currentMin;
    }
}