Min stack

Problem Design a stack supporting push, pop, top, and getMin — all in O(1).

Input / Output

• Operations: push(x), pop(), top(), getMin().

Constraints

• getMin must be O(1) — rescanning on demand defeats the purpose; O(n) space budget.

Example

• push −2, push 0, push −3 → getMin −3; pop → getMin −2.

Expected approach

• Auxiliary min-stack: push onto it when x <= current min; pop from it when the popped element equals its top — the min-stack top is always the current minimum. O(1) per op, O(n) worst-case extra space. Space refinements worth naming: store (value, min) pairs, push-only-on-new-min with counts for duplicates, or the O(1)-extra-space encoded-difference trick (store x − min, mutate min on pops) with its overflow caveat.