It’s been a while since I last posted an article on an algorithm and data structure problem. This time I decided to solve the Min Stack problem. In Min Stack you need to find the minimum element inside a stack in constant time. An alternate question is Max Stack where you have to find the maximum element in a stack. Both are pretty similar conceptually.
The problem explicitly states that each stack method should run at constant time – O(1).
This is the problem statement:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) — Push element x onto stack.
- pop() — Removes the element on top of the stack.
- top() — Get the top element.
- getMin() — Retrieve the minimum element in the stack.
Before continuing, make sure you try this problem yourself.