Min Stack — Track Mins in O(1)

This is a Medium design problem. It asks you to support push, pop, top, and getMin all in constant time. The catch is that a naive stack only gives you constant-time access to the top, not the minimum.

The Problem

Design a stack with the following operations:

• push(val) pushes val onto the stack.
• pop() removes the top element.
• top() returns the top element.
• getMin() returns the minimum element currently in the stack.

All four must run in O(1) amortized time.

Intuition

A list of values plus a min(self.data) call on every getMin is O(n) per query. We must precompute the minimum because we cannot afford to scan during the query.

Two designs hit O(1) per operation. The first keeps a second stack that records the running minimum; its top is always the current min. The second stores each element together with the minimum-so-far as a pair, so every entry is self-sufficient.

The critical subtlety in the parallel-stack version is using <= (not <) on push. If you push a value equal to the current minimum, you must record it again, otherwise a later pop of that value would not also pop the min stack and getMin would lie.

Explanation with Example

Perform push 3, push 5, push 2, push 2, getMin, pop, getMin, pop, getMin on the two-stack design.

• After push 3: stack [3], mins [3].
• After push 5: stack [3, 5], mins [3]. We do not push because 5 is larger than 3.
• After push 2: stack [3, 5, 2], mins [3, 2].
• After push 2: stack [3, 5, 2, 2], mins [3, 2, 2]. We push because the new value ties the current min.
• getMin returns 2.
• After pop: we remove 2 from both stacks. stack [3, 5, 2], mins [3, 2].
• getMin returns 2 again, which is correct because there is still a 2 in the stack.
• After pop: stack [3, 5], mins [3].
• getMin returns 3.

op            stack            mins
push 3        [ 3 ]            [ 3 ]
push 5        [ 3  5 ]         [ 3 ]
push 2        [ 3  5  2 ]      [ 3  2 ]
push 2        [ 3  5  2  2 ]   [ 3  2  2 ]
pop           [ 3  5  2 ]      [ 3  2 ]
pop           [ 3  5 ]         [ 3 ]
                                ^
                              getMin -> 3

Without the <= rule on push, the second push 2 would not have recorded the min, and the first pop would have left mins as [3] while the stack still contained a 2.

Code

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)

    def pop(self) -> None:
        val = self.stack.pop()
        if val == self.mins[-1]:
            self.mins.pop()

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

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

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> mins = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        if (mins.isEmpty() || val <= mins.peek()) mins.push(val);
    }
    public void pop() {
        int val = stack.pop();
        if (val == mins.peek()) mins.pop();
    }
    public int top() { return stack.peek(); }
    public int getMin() { return mins.peek(); }
}

class MinStack {
    stack<int> st, mins;
public:
    void push(int val) {
        st.push(val);
        if (mins.empty() || val <= mins.top()) mins.push(val);
    }
    void pop() {
        int val = st.top(); st.pop();
        if (val == mins.top()) mins.pop();
    }
    int top() { return st.top(); }
    int getMin() { return mins.top(); }
};

Edge Cases

• pop or top on an empty stack: the problem guarantees this will not happen, but in production code you should raise an error.
• Identical pushes: as shown above, the <= comparison is essential.
• Negative numbers: nothing special, the comparisons still work.
• Many duplicates of the same min: the parallel min stack can grow as large as the main stack in the worst case, which is fine and still O(n) total space.

Complexity Analysis

• Time: O(1) for every operation in both designs.
• Space: O(n) total, where n is the maximum number of elements present at once.

If amortized complexity is unfamiliar, the Big O notation refresher covers the basics.

How to Explain It in an Interview

• Restate the constraint: all four operations must run in constant time.
• Argue that you need to precompute the minimum because you cannot scan during getMin.
• Pick one of the two designs and explain it in one sentence.
• Call out the equality case explicitly. Saying it before the interviewer asks is a strong signal.
• Close with the space bound and mention the alternative design as a quick contrast.

Related Problems

• Max Stack, which adds a constant-time popMax.
• Implement Queue using Stacks, another design problem in the same family.
• Implement Stack using Queues, the mirror of the above.

For background on the structure powering both versions, see stacks and queues.

Wrap up

Min Stack is a clean lesson in trading a little extra memory for a major speedup. Nail the equality case and you have a solution that holds up under any test pattern.