Min Stack

Problem Description

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.

Implement the MinStack class:

• MinStack() initializes the stack.
• void push(int val) pushes val onto the stack.
• void pop() removes the element on top.
• int top() returns the top element.
• int getMin() returns the minimum element in the stack.

Examples

Constraints

• -2³¹ ≤ val ≤ 2³¹ - 1
• pop, top, and getMin are always called on non-empty stacks.
• At most 3 * 10⁴ calls total.

The Minimum Changes When You Push and Pop, So Track It Per Level

The naive getMin() scans the entire stack: O(n). To get O(1), you need to know the minimum without scanning. The insight: the minimum of the stack is determined by what’s currently in it. Every time you push a value, the new minimum is min(val, current_min). Every time you pop, the minimum reverts to whatever it was before that push.

If you record the minimum valid at each stack level, you can restore it in O(1) on every pop. A second “min stack” that runs parallel to the main stack does exactly this.

Solution 1: Scan on Every getMin (Baseline)

Store everything in a single list and scan for the minimum on demand.

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;

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

    public void push(int val) { stack.push(val); }
    public void pop() { stack.pop(); }
    public int top() { return stack.peek(); }

    public int getMin() {
        int min = Integer.MAX_VALUE;
        // scan entire stack to find the current minimum
        for (int val : stack) min = Math.min(min, val);
        return min;
    }
}

class MinStack:
    def __init__(self): self.stack = []
    def push(self, val): self.stack.append(val)
    def pop(self): self.stack.pop()
    def top(self): return self.stack[-1]
    def getMin(self):
        # scan entire stack to find the current minimum
        return min(self.stack)

#include <stack>
#include <climits>
#include <algorithm>

class MinStack {
    std::stack<int> stack;
public:
    void push(int val) { stack.push(val); }
    void pop() { stack.pop(); }
    int top() { return stack.top(); }
    int getMin() {
        std::stack<int> tmp = stack;
        int mn = INT_MAX;
        // scan entire stack to find the current minimum
        while (!tmp.empty()) { mn = std::min(mn, tmp.top()); tmp.pop(); }
        return mn;
    }
};

Complexity Analysis:

• Time Complexity: O(n) for getMin. All others O(1).
• Space Complexity: O(n).

Where it breaks: the problem explicitly requires O(1) for all operations. This approach fails that requirement.

Solution 2: Auxiliary Min Stack

Maintain a parallel minStack. On each push, also push the current minimum to minStack. On each pop, pop from both stacks. getMin() just peeks the top of minStack.

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

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

    public void push(int val) {
        stack.push(val);
        // record the minimum at this level so we can restore it on pop
        int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
        minStack.push(currentMin);
    }

    public void pop() {
        stack.pop();
        minStack.pop();  // restore the minimum from before this push
    }

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

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        # record the minimum at this level so we can restore it on pop
        current_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(current_min)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()  # restore the minimum from before this push

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

    def getMin(self) -> int:
        return self.min_stack[-1]

#include <stack>
#include <algorithm>
#include <climits>

class MinStack {
    std::stack<int> stack, minStack;
public:
    void push(int val) {
        stack.push(val);
        // record the minimum at this level so we can restore it on pop
        int currentMin = minStack.empty() ? val : std::min(val, minStack.top());
        minStack.push(currentMin);
    }

    void pop() {
        stack.pop();
        minStack.pop();  // restore the minimum from before this push
    }

    int top() { return stack.top(); }
    int getMin() { return minStack.top(); }
};

Complexity Analysis:

• Time Complexity: O(1) for all four operations.
• Space Complexity: O(n). Two stacks each holding at most n elements.

Where it breaks: uses 2x the space of a plain stack. If the interviewer asks for a space-optimized version, you can store pairs (value, min_at_this_point) in a single stack instead of two separate ones.

Why Not Store Only New Minimums in the Min Stack?

Some implementations push to minStack only when the new value is less than or equal to the current minimum, and pop from minStack only when the popped value equals the current minimum. This uses less space when there are many pushes that don’t change the minimum, but adds branching logic to pop. Both are O(1) time. The two-parallel-stacks version is simpler to get right under pressure.

Common Mistakes

• Popping minStack only sometimes (only when the value equals the current min). This gets out of sync with the main stack if you push the same minimum value twice. Simpler to always keep the stacks in sync.
• Not initializing minStack with the first value. If the first call is push(-2) and minStack is empty, you need a null check before peeking.
• Assuming getMin is called at most once. The stack can be pushed and popped multiple times between getMin calls. The minimum must be accurate at any point.

Frequently Asked Questions

Can you solve this with O(1) extra space (no second stack)? Yes. Store each element as a pair (value, current_min) in a single stack. Or use math tricks like storing 2*val - prev_min to encode the minimum without a second stack. Both work but are harder to explain under pressure. The auxiliary stack is the right answer in an interview.

What if INT_MIN is pushed? In the math encoding trick, subtracting prev_min from 2*val can overflow when val == INT_MIN. The auxiliary stack approach has no overflow risk since you’re just storing actual values.

What does this problem test in interviews? System design thinking at a small scale: can you maintain state about derived properties (minimum) efficiently as the data structure changes? It’s a good proxy for how you approach cache or auxiliary data structure design in larger systems.

← All Problems