Min Stack

Design a stack of integers that can also report its smallest element at any moment. Implement the class MinStack:

• MinStack() creates an empty stack.
• push(val) puts val on top of the stack.
• pop() removes the top element.
• top() returns the top element without removing it.
• getMin() returns the smallest element currently in the stack.

Every operation must run in O(1) time. pop, top and getMin are only called when the stack is not empty.

Each test is a sequence of calls; the expected output lists every call's return value, with null for the constructor, push and pop.

Example 1

Example 2

Example 3

Constraints

• -231 <= val <= 231 - 1
• pop, top and getMin are only called on a non-empty stack.
• At most 3 · 104 calls are made in total.

Pattern Path · Stacks · problem 44 of 169

Start simple

Use a normal stack and scan all elements on every getMin: O(n) per call.

The key idea

A stack only ever changes at the top, and that is what makes O(1) minimums possible. The minimum of the stack depends only on which elements are in it, and the elements below the top never change while the top exists. So the minimum "as of" each element can be computed once, when the element is pushed, and stays correct until the element is popped.

Store pairs (value, minimum so far). On push(val), the new minimum is val if the stack is empty, otherwise min(val, minimum stored at the current top). pop just removes the top pair, which automatically restores the previous minimum, because the pair below still records the minimum of the stack as it was before. top reads the value of the top pair and getMin reads its minimum.

All four operations touch only the top of the list, so each is O(1). A space-saving variant keeps a second stack that only receives a value when it is less than or equal to the current minimum; the <= is what keeps duplicate minimums correct.

Complexity

• Time: O(1) per operation
• Space: O(n)

Python

class MinStack:
    def __init__(self):
        # Each entry is (value, smallest value in the stack up to this entry).
        self.items = []

    def push(self, val: int) -> None:
        smallest = val if not self.items else min(val, self.items[-1][1])
        self.items.append((val, smallest))

    def pop(self) -> None:
        self.items.pop()  # the entry below still knows its own minimum

    def top(self) -> int:
        return self.items[-1][0]

    def getMin(self) -> int:
        return self.items[-1][1]

JavaScript

class MinStack {
  constructor() {
    // Each entry is [value, smallest value in the stack up to this entry].
    this.items = [];
  }

  push(val) {
    const n = this.items.length;
    const smallest = n === 0 ? val : Math.min(val, this.items[n - 1][1]);
    this.items.push([val, smallest]);
  }

  pop() {
    this.items.pop(); // the entry below still knows its own minimum
  }

  top() {
    return this.items[this.items.length - 1][0];
  }

  getMin() {
    return this.items[this.items.length - 1][1];
  }
}

What the interviewer is checking

It tests whether you can trade a little extra memory for constant-time queries by storing derived state alongside the data, and reason about invariants under pop.

Mistakes to avoid

• Keeping only one min variable, which is wrong after the minimum is popped.
• In the two-stack version, pushing to the min stack only on a strictly smaller value, which breaks when the minimum is duplicated.
• Comparing boxed Integer objects with == in Java instead of .equals.

Follow-ups to expect

• Can you use only O(1) extra space? (Store differences from the current min.)
• Also support getMax? (Store a running max too.)
• Build a queue with O(1) getMin? (Two min-stacks.)

In real software

Undo stacks that must show the best or worst state so far, and monotonic bookkeeping in trading systems (lowest price since a checkpoint), use the same "store the aggregate with each entry" idea.

Practice next