Skip to main content

155. Min Stack

medium

Design a stack that supports push, pop, top, and getMin — each in O(1). The 'auxiliary state' design pattern that shows up across many medium interview problems.

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: 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. You must implement a solution with O(1) time complexity for each function.

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
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]

Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recomputing the min on getMin is O(n). You need to remember it.

Hint 2

Keep a parallel stack of 'minimum so far'. Push the new minimum (or repeat the current one) on every push; pop in lockstep.

Hint 3

Space optimization: only push to the min-stack when the new value is <= current min, and only pop when the value being popped equals the min-stack's top.

Solution approach

Reveal approach

Maintain a primary stack of values and a parallel 'minStack' that always holds the minimum value present in the primary stack. On push(val): push val to the main stack; push min(val, minStack.top() if non-empty else val) to minStack. On pop: pop from both stacks. top: return main stack's top. getMin: return minStack's top. All operations O(1). For the follow-up 'optimize space': only push to minStack when val <= current min, and only pop from minStack when the value being popped equals the current min — but be careful with duplicates (use <= on push to handle them).

Complexity

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

Related patterns

  • stack
  • design

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Bloomberg
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Min Stack and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →