Skip to main content

14. Min Stack

easyAsked at Wix

Design a stack with O(1) min retrieval — Wix interviewers use this to test whether you can extend a basic data structure with auxiliary state, the same reasoning behind undo/redo stacks in the site editor.

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

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class with: MinStack() initializing the stack, void push(int val) pushing val onto the stack, void pop() removing the element on top, int top() getting the top element, and int getMin() retrieving the minimum element.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • pop, top, getMin 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
MinStack(); push(-2); push(0); push(-3); getMin(); pop(); top(); getMin();
Output
[-3, 0, -2]

Explanation: getMin returns -3, top after pop returns 0, getMin after pop returns -2

Example 2

Input
MinStack(); push(1); push(2); getMin(); pop(); getMin();
Output
[1, 1]

Approaches

1. Brute force

Use a single stack and scan all elements to find the minimum on each getMin call.

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

Tradeoff:

2. Auxiliary min stack

Maintain a parallel min stack that tracks the current minimum at every stack depth. Both stacks stay in sync, giving O(1) getMin.

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

Tradeoff:

Wix-specific tips

Wix grades you on recognising that the min is a per-depth property, not a global one — the moment you realise the parallel stack and say 'each push records the min at that depth', you've demonstrated the same invariant-tracking mindset the editor team uses when building undo history.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →