DSA Tracker

Visualize

Min Stack

Store each element alongside the minimum seen so far at that point in the stack: (value, minSoFar). Pushing recomputes minSoFar as min(newValue, previous top's minSoFar); popping simply reveals the minSoFar already stored one level down. getMin() becomes a plain O(1) read of the top pair.

Details

Animated on: Design a stack that supports push, pop, top, and getMin in O(1). Use a pair-stack where each element stores (value, minSoFar).

Problem:Min StackMedium

Stack

step 1 / 8

Step 1: Initialize empty MinStack. Stack is empty. No elements to point to.

Pseudocode
1MinStack: keep a stack whose items are pairs (value, minSoFar)
2push(val):
3  minSoFar = val if the stack is empty, otherwise the smaller of val and the top pair's minSoFar
4  push the pair (val, minSoFar) onto the stack
5end push
6pop(): remove the top pair from the stack
7top(): return the value of the top pair
8getMin(): return the minSoFar of the top pair

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Step 1: Initialize empty MinStack. Stack is empty. No elements to point to.
  2. Step 2: Push -2. Stack: [(-2, -2)]. The first element stores its own value as minSoFar: -2. getMin() returns -2.
  3. Step 3: Push 0. Stack: [(-2, -2), (0, -2)]. minSoFar for the new element is min(-2, 0) = -2. The -2 minimum is preserved below.
  4. Step 4: Push -3. Stack: [(-2, -2), (0, -2), (-3, -3)]. minSoFar = min(-2, -3) = -3. New top's minSoFar becomes -3.
  5. Step 5: Pop -3. Stack: [(-2, -2), (0, -2)]. minSoFar reverts to -2 (the new top's minSoFar). getMin() would now return -2.
  6. Step 6: Pop 0. Stack: [(-2, -2)]. minSoFar is -2 again. Top element still tracks the overall minimum.
  7. Step 7: getMin() returns -2 — the minimum across all elements ever pushed, confirmed by the pair-stack design. Each element's minSoFar preserves the running minimum from bottom up to that point.
  8. Step 8: Pop until stack is empty. Stack: []. On empty stack, getMin() would error. The pair-stack design ensures each level knows the minimum below it, making getMin() O(1) when the stack is non-empty.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Min Stack in the editorAll Stack problemsBack to roadmap