Design a stack that supports push, pop, top and getMin, each in O(1) time.
Before you code
One variable holding the minimum breaks as soon as you pop the minimum: what was the minimum before it? The stack needs to remember the minimum as it was at every depth.
Hints
- Push pairs:
(value, min(value, current_min)). The top pair's second element is always the minimum of the whole stack. - Popping a pair automatically restores the previous minimum, because the pair below stored it.
- Space-saving variant: keep a second stack that only receives a value when it is less than or equal to its own top. Why must equal values be pushed too?
Production & complexity notes
When solving Min stack on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Stacks and the LIFO rule to reinforce the underlying pattern.
What it practices
Storing a summary of everything beneath each entry, from Stacks and the LIFO rule.