Min stack

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

Requirements

• push(x), pop(), top(), getMin(), each O(1).

Areas to design

• How to answer getMin in O(1) without rescanning the stack.
• How the minimum is maintained across pops, including duplicate minimums.
• The space trade-off of the extra bookkeeping.

Example

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