Skip to main content

155. Min Stack

mediumAsked at Cisco

Min Stack at Cisco is a classic OOP design problem that tests whether you can augment a standard data structure to support an extra O(1) query. The interviewer wants the auxiliary-stack approach and is grading whether you remember to pop the aux stack when the data stack pops the current min.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-I and SDE-II interview reports cite Min Stack as a 30-minute round.
  • Levels.fyi (2025-11)— Cisco new-grad write-ups list this as a recurring OOP design problem.

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 run in O(1).

Constraints

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

Examples

Example 1

Input
push(-2); push(0); push(-3); getMin(); pop(); top(); getMin()
Output
[null,null,null,-3,null,0,-2]

Explanation: getMin returns -3 then -2 after the pop removed it.

Approaches

1. Brute-force: stack + linear scan for min

Push/pop on a single stack. getMin scans the whole stack.

Time
push/pop O(1), getMin O(n)
Space
O(n)
class MinStackBrute {
  constructor() { this.stack = []; }
  push(v) { this.stack.push(v); }
  pop() { this.stack.pop(); }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() {
    let m = Infinity;
    for (const v of this.stack) if (v < m) m = v;
    return m;
  }
}

Tradeoff: Fails the rubric — Cisco wants O(1) on every op including getMin. Useful only to show you understand what's being asked.

2. Two-stack: data stack + min stack (optimal)

Maintain a parallel stack holding the running min. On push: also push min(val, currentMin) onto the aux stack. On pop: pop both. getMin = peek the aux stack.

Time
O(1) per op
Space
O(n)
class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }
  push(v) {
    this.stack.push(v);
    const m = this.minStack.length ? Math.min(this.minStack[this.minStack.length - 1], v) : v;
    this.minStack.push(m);
  }
  pop() {
    this.stack.pop();
    this.minStack.pop();
  }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.minStack[this.minStack.length - 1]; }
}

Tradeoff: Doubles the space, but every op is O(1). The invariant — 'minStack[i] = min of stack[0..i]' — is the entire algorithm. Cisco interviewers expect this.

3. Single stack of [val, min] pairs

Same idea, packaged differently. Each entry stores both the value and the running min.

Time
O(1) per op
Space
O(n)
class MinStackPair {
  constructor() { this.stack = []; }
  push(v) {
    const m = this.stack.length
      ? Math.min(this.stack[this.stack.length - 1][1], v)
      : v;
    this.stack.push([v, m]);
  }
  pop() { this.stack.pop(); }
  top() { return this.stack[this.stack.length - 1][0]; }
  getMin() { return this.stack[this.stack.length - 1][1]; }
}

Tradeoff: Identical behavior but one less data structure. Slightly cleaner code; same memory cost. Pick whichever variant is more natural for you.

Cisco-specific tips

Cisco interviewers want the two-stack version because it generalizes — you can augment the aux stack with whatever derived state you want (running max, running sum, running variance). State the invariant out loud: 'minStack[i] is the min of stack[0..i] — so the top of minStack is always the current min, and popping both keeps the invariant valid.' That sentence is what they're listening for.

Common mistakes

  • Pushing val onto minStack only when val < currentMin — breaks O(1) pop because you can't tell whether to pop the aux stack.
  • Forgetting to handle the empty-stack case in push — first push must initialize the min to val.
  • Returning the wrong reference from top() (e.g., minStack instead of stack).

Follow-up questions

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

  • Max Stack (LC 716 premium) — supports both getMin and getMax in O(1).
  • Implement a queue using two stacks (LC 232).
  • Implement a stack using queues (LC 225).
  • Stack with O(1) average getMedian — heap-based variant.

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 always push to minStack, not just when value < min?

Because pop has to be O(1). If you only pushed conditionally, on pop you'd have to inspect 'was the popped value the current min?' — that's a comparison + a possible aux-stack pop. By pushing on EVERY push, the two stacks stay aligned and you always pop both. Trades a bit of memory for a much cleaner invariant.

Two-stack or pair-stack — does it matter?

Functionally equivalent. The two-stack version is slightly more flexible (you can extend with getMax by adding a third stack). The pair-stack version is fewer fields and slightly less code. Pick whichever you find clearer on the whiteboard.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Min Stack and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →