155. Min Stack

← All Problems
medium Stack
Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time. Implement the MinStack class with the following methods: push(val) pushes the element onto the stack, pop() removes the top element, top() returns the top element, and getMin() retrieves the minimum element currently in the stack. Methods pop, top, and getMin will always be called on non-empty stacks.

Example

Operations: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

  • push(-2), push(0), push(-3) – stack now contains [-2, 0, -3]
  • getMin() returns -3 – the smallest value currently in the stack
  • pop() removes -3 from the top
  • top() returns 0 – the new top element
  • getMin() returns -2 – with -3 removed, -2 is now the smallest
Maintain two stacks side by side — one stores the actual values, and the other tracks the current minimum at each level. Whenever you push a value, also push the new minimum (the smaller of the value and the current min) onto the min stack. This way getMin is always an O(1) peek.

Why this works

The trick is that the minimum can only change when you push or pop. By maintaining a second stack where each entry records “what is the minimum at this depth?”, you always know the current minimum by peeking at the top. When you pop, the previous minimum is automatically restored.

Step by step

  1. Push a value — push it onto the main stack. Also push min(value, current minimum) onto the min stack.
  2. Pop a value — pop from both stacks. The min stack automatically reverts to the previous minimum.
  3. Get the minimum — just peek at the top of the min stack. It always holds the minimum of all elements currently in the main stack.
Time: O(1) all ops Space: O(n) 
class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;  // parallel stack tracking the minimum at each level

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

    public void push(int val) {
        stack.push(val);
        int minVal = minStack.isEmpty() ? val : Math.min(val, minStack.peek());  // compare with current min
        minStack.push(minVal);
    }

    public void pop() {
        stack.pop();
        minStack.pop();  // keep both stacks in sync
    }

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

    public int getMin() {
        return minStack.peek();  // O(1) — always the current minimum
    }
}

class MinStack {
    stack<int> st;
    stack<int> minSt;  // parallel stack tracking the minimum at each level
public:
    MinStack() {}

    void push(int val) {
        st.push(val);
        int minVal = minSt.empty() ? val : min(val, minSt.top());  // compare with current min
        minSt.push(minVal);
    }

    void pop() {
        st.pop();
        minSt.pop();  // keep both stacks in sync
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return minSt.top();  // O(1) — always the current minimum
    }
};

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # parallel stack tracking the minimum at each level

    def push(self, val: int) -> None:
        self.stack.append(val)
        min_val = min(val, self.min_stack[-1] if self.min_stack else val)  # compare with current min
        self.min_stack.append(min_val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()  # keep both stacks in sync

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]  # O(1) — always the current minimum