Developers

Min Stack

MediumDesign a data structureGrade BAlso known as LeetCode 155

Design a stack with four operations: push(val), pop(), top() and getMin().

push adds a value on top. pop removes the top value. top returns the top value without removing it. getMin returns the smallest value currently in the stack.

Every operation must run in constant time. pop, top and getMin are only called when the stack is not empty.

Examples

Input MinStack(), push(5), push(3), push(7), getMin(), pop(), top(), getMin()
Output [null, null, null, null, 3, null, 3, 3]

Constraints

  • -1,000,000 <= val <= 1,000,000
  • At most 100,000 calls
  • pop, top and getMin are never called on an empty stack

Stuck? Take one hint at a time

Common mistakes
  • Keeping one variable for the minimum, which goes wrong after the minimum is popped.
  • Scanning the stack in getMin, which is linear.
  • In the two stack version, skipping a push of a duplicate minimum, which loses the minimum after one pop.
  • Reading the minimum from an empty stack when pushing the first value.
Questions an interviewer may ask next
  • Use less space: keep a second stack that only holds a value when it ties or beats the current minimum.
  • Add getMax in the same way.
  • Add a method that returns the middle value of the stack in constant time.
  • What changes if values can repeat? Check the second stack idea with duplicates.

How often this is reported

Commonly reported across 9 of 25 tracked companies
9/25

Grade B: Reported in more than one source. This reflects what candidates report, not a guarantee of what any company will ask.