Min Stack

Time — O(1): push, pop, top, and getMin are all constant time — optimal.
Space — O(k): the mins stack holds at most one entry per distinct running minimum (k ≤ n), fewer than one min per element.

Medium

Topics

StackDesign

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement MinStack with push(val), pop(), top(), and getMin().

Example 1

Input:  operations = ["MinStack","push","push","push","getMin","pop","top","getMin"], values = [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]

Constraints

-2^31 <= val <= 2^31 - 1
pop, top, getMin are only called on non-empty stacks.
At most 3*10^4 calls.

Run ⌘' · Submit ⌘⏎