Skip to main content

21. Min Stack

mediumAsked at Workday

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Workday uses this as a stand-in for 'efficient running aggregates' — the same pattern used for tracking the lowest pay-grade in a permission-stack snapshot.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 phone screen — design warmup.
  • LeetCode Discuss (2025)— Workday onsite — graded on the O(1) all-ops claim.

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: push(val), pop(), top(), getMin().

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.

Examples

Example 1

Input
MinStack m; m.push(-2); m.push(0); m.push(-3); m.getMin(); m.pop(); m.top(); m.getMin();
Output
-3, then 0, then -2

Explanation: getMin reads -3 (the minimum), pop removes -3, top reads 0, getMin now reads -2.

Approaches

1. Single stack, rescan on getMin

Push/pop normally; getMin scans the stack.

Time
push/pop/top O(1), getMin O(n)
Space
O(n)
class MinStack {
  constructor(){ this.s = []; }
  push(x){ this.s.push(x); }
  pop(){ return this.s.pop(); }
  top(){ return this.s[this.s.length-1]; }
  getMin(){ return Math.min(...this.s); }
}

Tradeoff: Easy but getMin is O(n) — violates the prompt.

2. Twin stack tracking running min

Keep a parallel stack where each entry is the min seen so far. Pop both together.

Time
all ops O(1)
Space
O(n)
class MinStack {
  constructor() { this.stack = []; this.mins = []; }
  push(val) {
    this.stack.push(val);
    const m = this.mins.length === 0 ? val : Math.min(val, this.mins[this.mins.length - 1]);
    this.mins.push(m);
  }
  pop() { this.stack.pop(); this.mins.pop(); }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

Tradeoff: O(n) extra space but O(1) on every op. The trick is that the min at each level is monotonic going down — we don't need to recompute.

Workday-specific tips

Workday loves this as a design question. State the O(1)-all-ops requirement explicitly, then justify the twin-stack space cost. Bonus: mention you can compress the min stack by storing (value, count) pairs to save space when many pushes don't change the min.

Common mistakes

  • Forgetting to pop the min stack — pops and tops get desynced.
  • Comparing val to mins[length-1] when mins is empty — needs the length-0 special case.
  • Storing the actual minimum value rather than the running min at each level — getMin then has to scan.

Follow-up questions

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

  • Compress with (value, count) pairs to save min-stack space.
  • Max Stack (LC 716).
  • Sliding Window Maximum (LC 239) — similar monotonic-structure idea.

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 push-time min monotonic in the stack?

Each level's min is the min of everything underneath. Popping the top can only raise the visible min, never lower it — so we just pop the corresponding min entry.

Can I do this with one stack?

Yes, by encoding (val, oldMin) tuples. Same complexity. Marginally less memory.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →