How do you implement a Min Stack (tracking minimum in O(1))?

Difficulty: 5/10

stack, auxiliary data structures, constant-time min

Min Stack

A Min Stack supports normal Stack operations while also returning the minimum element in O(1). A common design maintains a second stack containing the minimum value corresponding to each stack state.

javascript

1
Push: O(1).
2
Pop: O(1).
3
Peek: O(1).
4
GetMin: O(1).
5
Auxiliary space: O(n).
6
An alternative stores only values that establish new minimums, reducing typical auxiliary storage.

Scenario Questions

0-2 years experience

2-5 years experience

1Our product uses a min stack to track the lowest price in a sliding window of user actions. If we now need a 'removeBottom' operation that removes the element at the bottom of the stack, how does that affect your design?

Follow-up Questions