Min Stack
Medium · Stack & Strings · Stack · Design
Problem
Design a stack that also reports its smallest element, with every operation running in constant time:
- push(val) — put val on top
- pop() — remove the top item
- top() — return the top item
- getMin() — return the smallest item currently on the stack
Your tests replay a sequence of calls: the first names the class to construct, and each later entry is a method and its arguments. Operations that return nothing report None.
Examples
Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() Output: -3, then 0, then -2
getMin() returns -3 while it is on the stack, and -2 once it has been popped.
Constraints
- -2^31 <= val <= 2^31 - 1
- pop, top and getMin are only called on a non-empty stack
- Up to 3 * 10^4 calls
- Every operation must be O(1)
Approaches
- One stack of (value, minimum) pairs — time O(1) per operation, space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
