← Back to Python Examples

Min Stack

Design a stack that retrieves the minimum element in O(1) — by tracking minimums alongside values.

Contents

  1. The Problem
  2. The Insight
  3. The Solution
  4. Trace
  5. Variant — Space Optimization

1. The Problem

Design a stack that supports push, pop, top, and get_min — all in O(1) time.

# ms = MinStack()
# ms.push(-2)
# ms.push(0)
# ms.push(-3)
# ms.get_min()  → -3
# ms.pop()
# ms.top()      → 0
# ms.get_min()  → -2

The challenge: after popping -3, we still need to know that -2 is now the minimum. A single min variable fails here — popping an element can change the minimum.

2. The Insight

Store pairs: (value, current_min). Each stack entry records not just its value but what the minimum was at the time it was pushed. When you pop, the minimum is restored automatically — it's stored in the new top's pair.

3. The Solution

class MinStack:
    def __init__(self):
        self.stack = []  # stores (value, min_at_this_point)

    def push(self, val):
        current_min = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, current_min))

    def pop(self):
        self.stack.pop()

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

    def get_min(self):
        return self.stack[-1][1]


ms = MinStack()
ms.push(-2)
ms.push(0)
ms.push(-3)
print(ms.get_min())  # -3
ms.pop()
print(ms.top())      # 0
print(ms.get_min())  # -2
OperationTimeSpace
push / pop / top / get_minO(1)O(n) — two ints per entry

4. Trace

# push(-2): stack=[(-2, -2)]           min_so_far=-2
# push(0):  stack=[(-2,-2), (0,-2)]    min stays -2
# push(-3): stack=[(-2,-2),(0,-2),(-3,-3)]  new min=-3
# get_min() → stack[-1][1] = -3  ✓
#
# pop():    stack=[(-2,-2),(0,-2)]
# top()     → stack[-1][0] = 0   ✓
# get_min() → stack[-1][1] = -2  ✓
The minimum is automatically "restored" on pop because the previous entry already stored the correct minimum for that stack state. No extra logic needed.

5. Variant — Two-Stack Approach

Some solutions use two separate stacks: one for values, one tracking only minimums. The min-stack only pushes when a new minimum is seen.

class MinStack2:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # Only grows when a new min is seen

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

    def pop(self):
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

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

    def get_min(self):
        return self.min_stack[-1]
The two-stack approach uses less space when there are many consecutive pushes above the current minimum. The pair-tuple approach uses exactly 2× the space of a plain stack. Both are O(1) for all operations and both are accepted answers.