Skip to main content
DSA patterns

Min Stack

mediumStack and queue Must-doAmazonMicrosoftDatadog

Problem statement

Build a stack that supports the usual push, pop and top operations, plus one more: getMin, which returns the smallest value currently on the stack. Every one of these four operations must run in O(1) time — you're not allowed to scan the whole stack to answer getMin.

Implement a MinStack class with:

  • push(value) — adds value to the top of the stack.
  • pop() — removes the element on top of the stack.
  • top() — returns the element on top of the stack.
  • getMin() — returns the smallest element currently in the stack.

Think of it as a stack that always knows its own running minimum, the way a monitoring dashboard might keep a running "lowest free memory seen so far" figure that updates instantly as new readings come in and old ones get discarded.

Examples

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

Output: [null,null,null,null,-3,null,0,-2]

Explanation: MinStack() creates an empty stack. push(-2), push(0), push(-3) leave the stack holding -2, 0, -3 from bottom to top. getMin() returns -3, the smallest of the three. pop() removes -3, leaving -2 and 0. top() returns 0, the new top. getMin() now returns -2, the smallest of what's left.

Hints

Hint 1: A plain stack already gives you push, pop and top for free — the only new problem is answering "what's the minimum?" instantly, without looking through the whole stack.

Approach

Optimal: Single stack, encoded minimum

Intuition

The two-stack approach works, but it stores a full running-minimum value next to every single element, even though the minimum usually doesn't change from one push to the next. Instead, keep only one stack, and one variable, minVal, for the current minimum. Most pushes just store the value as normal. But when a value arrives that's smaller than minVal, instead of also remembering the old minimum somewhere else, encode it directly into the number you push: store 2 * value - minVal, then update minVal to the new value. That stored number comes out smaller than the new minVal, which is exactly the signal pop needs later: if the value you just popped is less than the current minVal, it wasn't a real value at all — it's a marker, and the real previous minimum can be recovered from it with 2 * minVal - poppedValue, undoing the same arithmetic.

Steps

  1. Keep one stack and a variable minVal.
  2. push(value): if the stack is empty, push value and set minVal = value. Otherwise, if value >= minVal, push value as-is. If value < minVal, push 2 * value - minVal (a marker smaller than the new minimum) and set minVal = value.
  3. pop(): pop the top of the stack. If that popped number is less than minVal, it was a marker — recover the previous minimum with minVal = 2 * minVal - poppedValue.
  4. top(): look at the top of the stack without removing it. If it's less than minVal, it's a marker, so the real top value is minVal itself; otherwise the value on top is the real value.
  5. getMin() just returns minVal.

Dry run

push(-2), push(0), push(-3):

call stack minVal what happened
push(-2) [-2] -2 stack was empty → store -2 as-is
push(0) [-2, 0] -2 0 ≥ -2 → store 0 as-is
push(-3) [-2, 0, -9] -3 -3 < -2 → store 2·(-3) - (-2) = -9, minVal becomes -3

getMin() returns minVal, -3. pop() pops -9; since -9 < the current minVal (-3), it's a marker, so minVal is restored with 2 * minVal - top = 2 * (-3) - (-9) = -6 + 9 = -2 — its value before the -3 was pushed — and the stack is now [-2, 0]. top() reads 0 directly (0 ≥ minVal, not a marker). getMin() returns minVal, -2 — the same answers as both earlier approaches.

Edge cases: this trick works with negative numbers exactly the same way as positive ones, since it's plain arithmetic rather than anything relying on sign. With values near the very edges of a 32-bit range, 2 * value can overflow a 32-bit integer, so the Java and C++ versions below carry the stack and minVal in a wider integer type to stay correct at the constraints' limits; Python integers don't have this problem.

Complexity

Time Every - operation is still O(1) — the same as the two-stack version, just with less memory per element.

Space O(n) - for the one stack of values, plus a single extra variable for the current minimum — no second stack the size of the first.

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

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(val)
            self.min_val = val
        elif val >= self.min_val:
            self.stack.append(val)
        else:
            self.stack.append(2 * val - self.min_val)
            self.min_val = val

    def pop(self) -> None:
        top = self.stack.pop()
        if top < self.min_val:
            self.min_val = 2 * self.min_val - top

    def top(self) -> int:
        top = self.stack[-1]
        return self.min_val if top < self.min_val else top

    def getMin(self) -> int:
        return self.min_val


if __name__ == "__main__":
    s = MinStack()
    out = [None]
    s.push(-2); out.append(None)
    s.push(0); out.append(None)
    s.push(-3); out.append(None)
    out.append(s.getMin())
    s.pop(); out.append(None)
    out.append(s.top())
    out.append(s.getMin())
    print(out)
RecapThe whole problem in a few lines, for the night before
  • Spot it: a stack that must also return its minimum in constant time
  • Idea: store the minimum so far next to every pushed value (or keep a second stack of minimums)
  • Cost: O(1) per operation, O(n) space
  • Trap: after a pop the minimum must go back to the earlier one; a single min variable forgets it

Interview follow-ups

  • Extend it to also support getMax() in O(1).

    Run the same idea twice, independently: keep a second running value maxVal alongside minVal, and a second encoding rule for pushes that exceed it (for the two-stack version, a second maxStack mirroring stack). The two trackers don't interact — a value can update the minimum, the maximum, both, or neither, and each is maintained with the same push/pop logic as its own counterpart.

  • What if you need getMin() over only the last k pushed elements, not the whole stack?

    That's a different problem — a sliding-window minimum instead of a whole-stack minimum, since elements now need to expire after k more pushes rather than only on an explicit pop. A monotonic deque (increasing from front to back) that also tracks each entry's "age" and evicts anything older than k pushes handles that in amortized O(1) per push, but it no longer maps onto a plain stack the way this problem does.

Frequently asked questions

It's the natural first idea and the easiest one to get right, so it's worth writing and testing before reaching for something cleverer — and it's a useful baseline to compare the faster approaches against. In an actual interview, you'd say up front that it doesn't meet the stated requirement and use it only as a stepping stone to the two-stack version.

Time and space are separate costs. Every operation being O(1) only means each individual call does a bounded, constant amount of work — it says nothing about how much memory the whole structure uses. minStack mirrors stack entry for entry, so together they still need memory proportional to how many values are on the stack.

It halves the memory compared to the two-stack version (one stack instead of two of the same size), which matters when the stack can hold up to 3 × 10⁴ values or more. In an interview, mentioning the two-stack solution first and then the single-stack refinement as a memory optimization shows you understand the space/time trade-off, which is often more valuable than jumping straight to the cleverest version.

A running minimum with instant push/pop shows up whenever you're tracking a "worst value so far" over a shrinking and growing window — lowest free disk space seen during a deploy, or the smallest available capacity across a rolling set of active nodes — without wanting to rescan everything on every check.