CodePark/ problems / Pile With Instant Minimum
START PRACTICINGPRACTICE
Coding problem · Data structures and algorithms › Stacks

Pile With Instant Minimum

easyabout 15 minutes in an interview

Write a class MinStack that holds a pile of numbers. It also reports the smallest number in the pile right now. You add to the top and remove from the top, so the last number added is the first one removed.

  • push(x: number): void puts x on top.
  • pop(): number removes the top number and returns it.
  • top(): number returns the top number without removing it.
  • getMin(): number returns the smallest number currently in the pile.

Rules:

  • Every method must run in O(1) time, which means the same small amount of work however big the pile is. So getMin can't scan the pile.
  • pop, top and getMin throw an Error when the pile is empty.
  • Numbers can be negative and can repeat.
Input: push(5), push(2), push(4), getMin() Output: 2
Input: …then pop(), pop(), getMin() Output: 4, 2, 5pop returns 4, then 2. Once 2 is gone, the minimum is 5 again.