Challenge: Constant-Time Min-Element Stack

Here’s another problem from the Algorithm Design Manual (Skiena), Interview Problem 4-44:

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?
Hint 1
Constant time? Well then it’s stacks all the way down.
Hint 2
Two stacks, to be exact.
Answer
Data structure contains two stacks, all and mins. mins.top() is the minimum element. After calling all.push(), push to mins if all.top() <= mins.top(). Before calling all.pop(), pop from mins if all.top() == mins.top().

Leave a Reply

Your email address will not be published. Required fields are marked *