Min Stack

Difficulty: Medium

Problem

Build a stack that, besides the usual operations, can report its smallest value instantly. Implement the MinStack class: MinStack() creates an empty stack, void push(int val) adds val on top, void pop() removes the top item, int top() returns the top item, and int getMin() returns the smallest item currently stored. Every operation must take 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) fill the stack; getMin() returns -3; pop() removes -3; top() then returns 0; getMin() now 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)

Pseudocode

class MinStack:
    function init():
        stack = []
        minStack = []
    
    function push(val):
        stack.push(val)
        if minStack is empty or val <= minStack.top():
            minStack.push(val)
    
    function pop():
        if stack.top() == minStack.top():
            minStack.pop()
        stack.pop()
    
    function top():
        return stack.top()
    
    function getMin():
        return minStack.top()

Hints

  • Use two stacks: one for normal operations, one to track minimums
  • Push to the min stack only when the new value is ≤ current minimum
  • Pop from the min stack only when the popped value equals the current minimum

Complexity questions

What is the time complexity of getMin() in the brute force approach?

O(n). The brute force scans all n elements in the stack to find the minimum → O(n).

What is the time complexity of getMin() in the two-stack approach?

O(1). getMin() simply peeks at the top of the min stack → O(1).

What is the worst-case space complexity of the two-stack approach?

O(n). In the worst case (strictly decreasing sequence), both stacks hold all n elements → O(n) extra space.

Check your understanding of Min Stack

What operations must a MinStack support, and in what time complexity?

push, pop, top, getMin: all in O(1). The MinStack must support push, pop, top, and getMin all in O(1) constant time. This is the key constraint of the problem.

After push(5), push(3), push(7), what should getMin() return?

3 (the smallest value in the stack). getMin() returns the minimum element currently in the stack. The stack contains [5, 3, 7], and the smallest is 3.

After push(-2), push(0), push(-3), pop(), what does getMin() return?

-2. After popping -3 (which was the min), the min stack's new top is -2, the previous minimum.

Related problems

Keep practising