155. Min Stack

Q: Why is the always-push-to-mins variant preferred over the conditional-push variant?

Because pop is branchless — you always pop both stacks in lockstep, no need to compare to know whether to also pop mins. Conditional-push saves space on inputs with many non-decreasing pushes but adds bug surface to pop.

Q: Why must the conditional-push variant use `<=` instead of `<`?

Because duplicates need to be tracked. If you only push when strictly smaller, and the input is push(1), push(1), pop(), then after the pop, mins still has 1 at the top — correct. But if your push code used `<` and you pop the value 1, the mins top would already have been the previous 1 still standing — and pop would over-pop. The `<=` ensures every duplicate gets its own mins entry.

mediumAsked at Twilio

Min Stack is Twilio's auxiliary-state-tracking probe: design a stack that supports push, pop, top, and getMin all in O(1). The grading rubric weighs whether you maintain a parallel structure (second stack of running minimums) rather than scanning to compute min on demand.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Twilio loops.

Glassdoor (2026-Q1)— Listed in Twilio backend SWE on-site reports as a 'design with invariant' question.
LeetCode Discuss (2025-11)— Cited in Twilio platform-engineering interview reports.

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 object; void push(int val) pushes the element val onto the stack; void pop() removes the element on the top of the stack; int top() gets the top element of the stack; int getMin() retrieves the minimum element in the stack. All operations must be in O(1) time.

Constraints

-2^31 <= val <= 2^31 - 1
Methods pop, top and getMin are called on non-empty stacks.
At most 3 * 10^4 calls will be made.

Examples

Example 1

Input

push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Output

[null,null,null,-3,null,0,-2]

Explanation: Standard sequence — getMin returns -3 while -3 is on top, then -2 after the pop.

Approaches

1. Single stack with O(n) getMin (rejected)

Push to a single stack; on getMin, scan the whole stack.

Time: push/pop/top O(1), getMin O(n)
Space: O(n)

class MinStackBrute {
  constructor() { this.s = []; }
  push(v) { this.s.push(v); }
  pop() { this.s.pop(); }
  top() { return this.s[this.s.length - 1]; }
  getMin() {
    let m = Infinity;
    for (const v of this.s) if (v < m) m = v;
    return m;
  }
}

Tradeoff: Misses the O(1)-getMin contract. Twilio rejects this on the rubric — the question explicitly tests whether you can design auxiliary state that maintains the invariant.

2. Two stacks — values + running minimums (optimal)

Push every value to one stack; push the new running minimum to a parallel min-stack so its top always holds the current min.

Time: O(1) per op
Space: O(n)

class MinStack {
  constructor() {
    this.s = [];
    this.mins = []; // parallel stack of running mins
  }
  push(val) {
    this.s.push(val);
    const m = this.mins.length === 0 ? val : Math.min(val, this.mins[this.mins.length - 1]);
    this.mins.push(m);
  }
  pop() {
    this.s.pop();
    this.mins.pop();
  }
  top() {
    return this.s[this.s.length - 1];
  }
  getMin() {
    return this.mins[this.mins.length - 1];
  }
}

Tradeoff: Always push to the mins stack — even when the new value isn't smaller — so pop never has to look up whether to also pop the mins stack. Branchless pop is the elegance bit.

3. Single stack of [val, currentMin] pairs (space-equivalent alternative)

Each entry on the stack carries the running minimum at that point.

Time: O(1) per op
Space: O(n)

class MinStackPaired {
  constructor() { this.s = []; }
  push(val) {
    const m = this.s.length === 0 ? val : Math.min(val, this.s[this.s.length - 1][1]);
    this.s.push([val, m]);
  }
  pop() { this.s.pop(); }
  top() { return this.s[this.s.length - 1][0]; }
  getMin() { return this.s[this.s.length - 1][1]; }
}

Tradeoff: Same asymptotics, half the bookkeeping but every entry now allocates a pair. Either approach is acceptable at Twilio; the two-stacks version is canonical.

Twilio-specific tips

Twilio's bar on Min Stack is that you maintain auxiliary state synchronously with the main operations. State the invariant out loud: 'after every push, mins[top] equals the minimum of all values currently in the main stack'. The space-optimized variant (push to mins only when the new value is <= the current min) is a common follow-up — make sure you understand why it requires the `<=` (not strict `<`) to handle duplicates.

Common mistakes

Using strict `<` in the space-optimized variant — fails on inputs like push(1), push(1), pop(), getMin() because the second 1 isn't pushed to mins, then the pop incorrectly thinks min should be updated.
Forgetting to pop the mins stack synchronously with the value stack.
Computing min in pop() (looking at the next-most-recent value) — that's O(n) in the worst case and breaks the contract.

Follow-up questions

An interviewer at Twilio may pivot to one of these next:

Can you do it without a second stack? (Yes — encode each push as `2*val - currentMin` and decode on pop; trick problem from competitive programming. Beware integer overflow.)
How would you adapt to a MAX stack? (Same skeleton — track running max instead.)
How would you support arbitrary order statistics (kth smallest) in O(log n)? (Replace the min stack with a multiset / order-statistic tree.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the always-push-to-mins variant preferred over the conditional-push variant?