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 Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

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

Asked at

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

Amazon
Meta
Google
Bloomberg
Microsoft