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. pop, top and getMin are only ever called on a non-empty stack.

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: A stack only changes at the top, so the smallest of everything from the bottom up to a box can be written on it once, when it arrives, and stays true while the box is there. getMin() is the top box's note.

Let every box remember the smallest value at or below it: a pair (value, low), or a second stack holding one note per box. All operations become O(1).

Steps

  1. Initialize an empty stack of pairs (value, low), where low is the smallest value at or below that box
  2. push(val): low = val if the stack is empty, else min(val, top.low). Push (val, low)
  3. pop(): remove the top pair (the box and its note leave together)
  4. top(): return top.value
  5. getMin(): return top.low
  6. Optional space-saving variant: a second stack holding only new minimums (push when val ≤ its top, pop when the popped value equals its top)

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

Pseudocode

class MinStack:
    # every box remembers the smallest value at or below it
    function init():
        stack = []            # pairs (value, low)
    
    function push(val):
        low = val
        if stack is not empty:
            low = min(val, stack.top().low)
        stack.push((val, low))
    
    function pop():
        stack.pop()           # the box and its note leave together
    
    function top():
        return stack.top().value
    
    function getMin():
        return stack.top().low

# Space-saving variant (same idea, fewer notes): keep a second stack
# that only stores new minimums.
#   push(val): stack.push(val); if minStack is empty or val <= minStack.top(): minStack.push(val)
#   pop():     if stack.top() == minStack.top(): minStack.pop();  then stack.pop()
#   getMin():  return minStack.top()
# It needs <= (not <): on a tie the second copy must keep its own note.

Hints

  • Each entry remembers the minimum at the time it was pushed: store a pair (value, smallest at or below this box), or a second pile with one note per box
  • A push makes its note from the box below: the smaller of the new value and that note (the value itself on an empty stack). A pop removes the box and its note together, so getMin is just the top's note
  • Space-saving variant: use a second stack that only stores new minimums. Push to it when the new value is ≤ the current minimum, and pop from it only when the popped value equals the current minimum
  • A tie needs ≤ (not <) so that the second copy keeps its own note: with push(2), push(2), pop(), the first 2 must still be in the min stack

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() when every box carries a min note?

O(1). getMin() simply reads the note on the top box → O(1).

What is the worst-case space complexity of the note-on-every-box approach?

O(n). One note per box: n boxes carry n notes → O(n) extra space. (The space-saving variant that stores only new minimums also needs O(n) in the worst case, a strictly decreasing sequence.)

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 new top box is (0) and its note says -2, the previous minimum.

Related problems

Keep practising