← Microsoft questions

Design a Stack with O(1) min operation

Filed under Microsoft · Also reported at Zilingo

Free read 1 of 3

Ensure all standard stack operations must be supported alongside min in O(1) time.

The question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Constraints

  • Methods push, pop, top, and getMin will be called on non-empty stacks.
  • O(1) time complexity for each function.

Examples

Input
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
Output
As described
Why
Maintains minimum tracking across state changes.

Approach

  1. Ensure all standard stack operations must be supported alongside min in O(1) time.

Solution

O(1) time for all operations, O(n) space

Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Tips

  • What they are testing: Test duplicate minimum values to ensure pop operations correctly handle removing one instance while keeping the prior minimum.
  • Common mistake: Updating the min tracker only when a strictly smaller value is pushed, which fails when duplicate minimums are popped.

Related Microsoft questions

Collected from public candidate posts and coding forums. Updated Nov 2026.