LeetCode Min Stack: Track Mins in O(1)

LeetCode 155, Min Stack, 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. We will solve it two ways, both of which run in O(1) per operation, and discuss the small bookkeeping details that interviewers probe.

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.

Brute Force

You could store values in a list and recompute the minimum on every getMin call by scanning the list.

class MinStack:
    def __init__(self):
        self.data = []
    def push(self, val): self.data.append(val)
    def pop(self): self.data.pop()
    def top(self): return self.data[-1]
    def getMin(self): return min(self.data)

This is correct but getMin is O(n). The problem explicitly requires constant time, so this version fails on the design intent even if it passes some test cases.

Optimal Solution

Two designs hit O(1) per operation. Pick whichever you find clearer.

Two parallel stacks

Maintain a second stack that records the running minimum. The top of the min stack is the minimum of all values currently in the main stack.

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]

The key subtlety is the <= 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.

Stack of pairs

Store each element together with the minimum seen so far. Every entry is self-sufficient.

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

    def push(self, val: int) -> None:
        cur_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, cur_min))

    def pop(self) -> None:
        self.stack.pop()

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

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

This version uses slightly more memory per element but the code is simpler and there is no equality bug to worry about.

Walk Through an 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: we remove 2 from both stacks. stack [3, 5], mins [3].
• getMin returns 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. That bug is the single most common mistake on this problem.

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. The pair design uses two integers per slot, the parallel design uses one integer per slot plus a smaller min stack.

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

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

For background on the structure powering both versions, see stacks and queues. If you continue into harder design problems, hashing and hash maps shows the next building block you will reach for.

Wrap up

Min Stack is a clean lesson in trading a little extra memory for a major speedup. Whether you keep a parallel stack of running minima or store the minimum alongside each value, the punchline is the same: precompute what you cannot recompute fast. Nail the equality case and you have a solution that holds up under any test pattern an interviewer can throw at it.