Data Structures
Min-Stack
push, pop, peek, getMin: all O(1) — the mini stack means you never have to scan the whole stack to find the minimum.
The idea, in plain English
A min-stack is like a pile of plates, where each plate secretly remembers the smallest number in the whole pile at the moment it was placed. You can only see the top plate. But that top plate's secret note always tells you the smallest number in the whole pile, instantly, with no digging.
How it works
- 1Keep two stacks side by side: a main stack for the actual values, and a mini stack that tracks the running minimum.
- 2push(x): push x onto the main stack. Also push onto the mini stack whichever is smaller: x, or the mini stack's current top. If the mini stack is empty, just push x.
- 3pop(): pop from both stacks together, so they always stay the same size and in sync.
- 4getMin(): just peek at the top of the mini stack — the smallest value is always sitting right there.
When you'd use it
Use a min-stack anywhere you need normal stack behavior, like push, pop, and peek, plus an instant answer to 'what's the smallest value in here right now?' You avoid scanning the whole stack every time.
Common beginner mistakes
- Don't pop from only the main stack and forget the mini stack. If you do, the two stacks fall out of sync, and getMin() starts giving wrong answers.
- Don't assume you need to search for the new minimum on every push. Just compare the new value to the mini stack's current top.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
Min: 1
Pop: 1
Min: 2
Pop: 7
Min: 2See it in motion
Ready. Two stacks in lock-step — the min stack's top is always the smallest value, read in O(1).
Not sure this is the right topic? See the learning paths → or where this leads →