Skip to content
Onsite
9 / 28

Min Stack

MediumP1Coding

Design a stack that supports push, pop, top and retrieving the minimum element, each in O(1) time.

Implement the MinStack class:

  • MinStack() creates an empty stack.
  • push(val) pushes val onto the stack.
  • pop() removes the top element.
  • top() returns the top element.
  • getMin() returns the smallest element currently in the stack.

pop, top and getMin are only called on a non-empty stack.

Example 1

Input
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Why
The minimum is -3; after popping it, the top is 0 and the minimum is -2.

Constraints

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

Hints

Run checks the 3 visible tests, Submit all 5.