Min Stack

Difficulty: Medium

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack, void push(int val) pushes the element val, void pop() removes the top element, int top() gets the top element, int getMin() retrieves the minimum element in the stack. Each function must run in O(1) time.

Example

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[], [-2], [0], [-3], [], [], [], []]
Output: [null, null, null, null, -3, null, 0, -2]
Explanation: push(-2), push(0), push(-3) → getMin() returns -3 → pop() removes -3 → top() returns 0 → getMin() returns -2.

Brute-force approach

Use a single stack for push/pop/top. For getMin(), scan the entire stack each time to find the minimum.

Steps

  1. Use a regular stack/list for push, pop, top
  2. For getMin(): scan the entire stack for the minimum
  3. Return the minimum found

Time complexity: O(n) for getMin, O(1) for others · Space complexity: O(n)

Trade-offs

  • getMin() takes O(n) time on every call
  • Repeated getMin() calls make it very inefficient
  • Not suitable when minimum is queried frequently

Optimal approach

Key insight: By maintaining a parallel 'min stack', each push/pop keeps the minimum in sync, so getMin() is always just a peek at the min stack's top.

Use two stacks: a main stack for values and a min stack that tracks the minimum at each level. All operations become O(1).

Steps

  1. Initialize main stack and min stack
  2. push(val): push to main. If val ≤ minStack.top (or minStack empty), push to minStack too
  3. pop(): if main.top == minStack.top, pop minStack. Always pop main
  4. top(): return main.top
  5. getMin(): return minStack.top

Time complexity: O(1) for all operations · Space complexity: O(n)