A stack that reports its minimum in O(1)

Imagine a chart tool where the user pushes and pops data points and the axis label must always show the current smallest value. Recomputing the minimum on every change is O(n) each time; a min stack gives it to you in constant time.

Implement a MinStack class holding numbers. It is constructed with no arguments and starts empty. push(value) adds a number on top and returns the new size. pop() removes and returns the top number, or undefined when empty. peek() returns the top number without removing it, or undefined when empty. min() returns the smallest number currently in the stack, or undefined when empty, without scanning the whole stack. size() returns how many numbers are held.

The minimum must stay correct as values are popped: if the smallest value is removed, min() reports the next smallest of what remains. Duplicate values count separately, so pushing the same minimum twice and popping once still leaves that minimum in place.

What it has to do

• min() returns the smallest value currently in the stack.
• min() stays correct after values are popped, including duplicates of the minimum.
• min(), pop() and peek() return undefined on an empty stack.
• min() must not scan the whole stack on each call.
• push returns the new size.

Your workspace