Design a stack that supports the usual push, pop, and top, plus a getMin operation that returns the smallest element currently on the stack — and make every one of those four operations run in O(1) time. The trick is to never actually compute the minimum on demand. A second, parallel stack tracks it incrementally: every time a value is pushed, the min-stack also gets a push — either the new value itself (if it's smaller than or equal to the current minimum) or a repeat of the current minimum (if the new value is bigger and doesn't change anything). Every pop removes from both stacks together, so the min-stack's top is automatically correct for whatever remains. getMin then becomes nothing more than reading the min-stack's top — the minimum was already known the instant it was needed, because it was maintained the whole time, not searched for.