Min Stack
Maintained by Vikas D, software engineer
You are designing a stack with one extra power: at any moment you can ask for the smallest value currently stored, and that answer must come back instantly rather than by scanning the whole stack.
Instead of wiring up a class with separate methods, this version hands you the calls as data. You receive an array of operation names ("push", "pop", "top", "getMin") and a parallel array of argument lists. A "push" call carries one number in its argument list; the other three carry an empty list.
Walk through the operations in order and produce an array of results, one entry per operation. Use null for any call that returns nothing (push and pop), the current top value for "top", and the current minimum for "getMin".
You are promised that pop, top, and getMin only ever run while the stack holds at least one element, so you never have to defend against an empty stack.
Examples
After pushing -2, 0, -3 the minimum is -3. Pop removes -3, so the top is now 0 and the minimum climbs back to -2.
With 5 then 3 on the stack the minimum is 3. Popping 3 leaves only 5, so the minimum becomes 5 again.
A single pushed value is both the top and the minimum.
Constraints
- Values fit in a 32-bit signed integer: -2^31 <= val <= 2^31 - 1.
- pop, top, and getMin are only called when the stack is non-empty.
- At most 3 * 10^4 operations are issued in total.
- push, pop, top, and getMin must each run in O(1) time.
Visible test cases
- minStack(["push","push","push","getMin","pop","top","getMin"], [[-2],[0],[-3],[],[],[],[]]) == [null,null,null,-3,null,0,-2]
- minStack(["push","push","getMin","pop","getMin"], [[5],[3],[],[],[]]) == [null,null,3,null,5]
- minStack(["push","push","push","getMin"], [[1],[2],[3],[]]) == [null,null,null,1]
- minStack(["push","top","getMin"], [[42],[],[]]) == [null,42,42]
Hints
Hint 1
The hard part is getMin. Scanning the stack on every query would be O(n) per call, so you need to know the answer in advance without searching.
Hint 2
What if every element remembered the minimum of the stack at the moment it was pushed? Then the minimum of the whole stack is just whatever the top element recorded.
Hint 3
Keep a second stack that runs in lockstep with the main one: each time you push a value, also push min(value, current recorded minimum). Popping both stacks together keeps the recorded minimum correct.
Approaches
Rescan on every getMin
Time O(1) for push, pop, top; O(n) per getMin · Space O(n)Store values in a plain stack and compute the minimum by looping over all of them whenever getMin is asked.
- Keep one list acting as the stack.
- push appends, pop removes the last item, top reads the last item.
- For getMin, iterate the entire list and return the smallest value.
Paired minimum stack
Time O(1) per operation · Space O(n)Maintain a second stack where each slot holds the minimum of everything at or below it, so the current minimum is always the top of that stack.
- Keep the value stack and a parallel mins stack.
- On push, append the value, then append min(value, previous mins top) (or the value itself if mins is empty).
- On pop, remove the top of both stacks together.
- top returns the value stack's last element; getMin returns the mins stack's last element.
Common mistakes
- Recomputing the minimum by scanning on each getMin call breaks the constant-time requirement once there are many elements.
- Forgetting to pop the minimum stack in lockstep with the value stack leaves a stale minimum after a pop.
- Tracking only a single min variable fails: when you pop the current minimum you have no way to recover the previous one, which is exactly why the paired stack stores history.
- Seeding the first minimum incorrectly. The very first push has no prior minimum to compare against, so its recorded minimum is the value itself.
- Pushing a result for top or getMin but returning null for push or pop swaps which calls produce output; only push and pop contribute null.
Follow-up variations
- Support getMax in the same constant time alongside getMin.
- Reduce the extra space by only pushing onto the minimum stack when a value is less than or equal to the current minimum, storing counts or repeated minima carefully.
- Implement the same constant-time minimum guarantee for a queue instead of a stack.
- Make the structure thread-safe or describe how concurrent push and pop would interact.