Min Stack

Build a stack that returns its current minimum in constant time.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Min Stack: Store each value with the minimum for its entire stack prefix, so the top pair always answers get_min().

Input and goalBuild a stack that returns its current minimum in constant time.

Initialize an empty MinStackBefore any operation, the pair stack is empty.

emptytopempty

columnsvalue | minimum so farlayoutbottom to topoperationspush(5), push(2), push(4), get_min(), pop(), get_min(), top()actioninitialize

Recognize it

Use this pattern when ordinary stack operations must also answer an aggregate such as the current minimum in constant time, including immediately after pops.

Keep true

For every stored pair (value, minimum), minimum equals the smallest value from the bottom through that pair; therefore the top pair summarizes the complete current stack.

Reuse it

Attach any reversible prefix summary needed later to each stack item; the same technique supports max stacks, depth summaries, and constant-time aggregate reads after rollback.

Pattern: Store the answer needed later with each item.

Simple idea: Save (value, minimum so far) for every pushed value. When an item is removed, the earlier minimum is already stored under it.

class MinStack:
   def __init__(self) -> None:
      self.stack: list[tuple[int, int]] = []

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

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

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

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

Cost: $O(1)$ time per operation and $O(n)$ space.