Min Stack

Interview Prep

Warm-upStackstackdesign

The problem

Design a stack that supports push, pop, top, and getMin — all in O(1) time. The challenge: getMin must not scan the stack.

Pattern: keep an auxiliary running-minimum stack

The clean answer pairs each pushed element with an entry in a second stack that holds the minimum-so-far. Push x onto the min-stack only if it's ≤ the current minimum (use ≤, not <, so duplicates survive pops correctly). On pop, peel from the min-stack only if the popped element matches its top.

Every operation is O(1). The min-stack has size at most n, so the memory overhead is at most 2× the main stack — typically much less if the data isn't monotone decreasing. 

class MinStackSlow:
    """getMin is O(n) — recompute every time."""
    def __init__(self): self.s = []
    def push(self, x): self.s.append(x)
    def pop(self):     self.s.pop()
    def top(self):     return self.s[-1]
    def getMin(self):  return min(self.s)

Solution: two stacks

class MinStack:
    """Auxiliary stack of running minima. All ops O(1)."""
    def __init__(self):
        self.s: list[int] = []
        self.m: list[int] = []   # m[-1] is always min(s) when s is non-empty

    def push(self, x: int) -> None:
        self.s.append(x)
        if not self.m or x <= self.m[-1]:
            self.m.append(x)

    def pop(self) -> None:
        x = self.s.pop()
        if x == self.m[-1]:
            self.m.pop()

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

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

Trace

Operations:  push 3, push 5, push 2, push 1, getMin, pop, getMin, pop, getMin

State (two-stack version):

push 3:  s=[3]       m=[3]    (3 is new min)
push 5:  s=[3,5]     m=[3]    (5 > 3, m unchanged)
push 2:  s=[3,5,2]   m=[3,2]
push 1:  s=[3,5,2,1] m=[3,2,1]

getMin -> 1
pop:     s=[3,5,2]   m=[3,2]   (popped 1 was top of m)
getMin -> 2
pop:     s=[3,5]     m=[3]     (popped 2 was top of m)
getMin -> 3

O(1)-extra-space variant: encoded deltas

A cute variant uses a single stack and a tracked cur_min. Push x − cur_min instead of x; whenever the difference is negative, we know x is a new minimum, so we update cur_min to x. Pop reverses the trick. Total extra memory is one integer beyond the stack itself. 

class MinStackEncoded:
    """Single stack, O(1) extra space (one int besides the stack itself).
    Store 'delta from current min'; track the current min separately.
    """
    def __init__(self):
        self.s: list[int] = []
        self.cur_min: int = 0     # only valid when stack is non-empty

    def push(self, x: int) -> None:
        if not self.s:
            self.s.append(0)
            self.cur_min = x
        else:
            self.s.append(x - self.cur_min)   # may be negative
            if x < self.cur_min:
                self.cur_min = x

    def pop(self) -> None:
        top = self.s.pop()
        if top < 0:
            # popping a new-minimum element; recover the old min
            self.cur_min = self.cur_min - top

    def top(self) -> int:
        return self.s[-1] + self.cur_min if self.s[-1] >= 0 else self.cur_min

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

Slick, and a useful demonstration that you can sometimes trade an auxiliary structure for cleverly-encoded extra state. In practice the two-stack version is preferred for clarity unless space is at a premium.

Complexity

Variations worth knowing