Min Stack

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Design a stack that supports push(x), pop(), top() and getMin(), all in O(1) time. getMin returns the smallest value currently in the stack. You may assume pop, top and getMin are only called on a non-empty stack.

    A short design question about remembering history: the minimum changes when you pop, and you can't afford to search for it again. It is often asked as its mirror, a Max Stack, where the hard part is an extra popMax(); that version is covered below. Original problem: LeetCode 155 (Max Stack: LeetCode 716).

    Example

    While 2 is in the stack the minimum is 2; once 2 is popped, the minimum has to return to 5.
    While 2 is in the stack the minimum is 2; once 2 is popped, the minimum has to return to 5.
    push(5); push(2); push(7)
    getMin() -> 2
    pop()    -> 7
    pop()    -> 2
    getMin() -> 5

    Constraints (assumed)

    • Up to 3 × 10⁴ calls; values fit in a 32-bit integer.

    What this question tests

    • Noticing that a single minimum variable can't be restored after a pop.
    • Augmenting a data structure: storing extra information alongside each element.
    • For the Max Stack version: combining a stack with a heap or ordered map and keeping them consistent.

    Questions to ask first

    1. Can the stack be empty when getMin is called? (Here: no. Otherwise decide whether to throw or return a sentinel.)
    2. Can values repeat? (Yes, and duplicates of the minimum are the classic trap.)
    3. Does pop need to return the value? (Here: yes, it is handy.)
    4. Is it a min stack, a max stack, or both? If there is a popMax/popMin, the design changes.