Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Min Stack

LeetCode #155Medium
O(1) getMin · a twin min-stack

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.

Asked atAmazonBloombergGoogle
step 1 / 10
top ↓
(empty)
stack (empty)
Twin min-stack
▸
1// keep stack `main` and stack `mins` in lockstep
2push(x):  main.push(x); mins.push(min(x, mins.top))
3pop():    main.pop();   mins.pop()
4top():    return main.top()
5getMin(): return mins.top()
state
  • minStack[]
  • getMin—

line 1A normal stack does push/pop/top in O(1), but finding the MINIMUM would need an O(n) scan. Fix: keep a second “min stack” in lockstep. Each entry stores the smallest value seen at or below its level, so getMin is just minStack.top — O(1).