Min Stack — Medium Coding Interview Question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: - push(val): pushes val onto the stack - pop(): removes the top element - top(): gets the top element - getMin(): retrieves the minimum element in the stack All operations must be O(1) time complexity.

Example

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Output: -3, 0, -2

Constraints

• -2³¹ ≤ val ≤ 2³¹ - 1
• Methods pop, top, and getMin will always be called on non-empty stacks.

Topics & Companies

Topics: stack

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg, Adobe

Optimal Solution Complexity

Time complexity: O(1) for all operations. Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns