Design a stack that supports getMin() in O(1) time and O(1) extra space

I came across this interview question the other day, and when I saw the solution, I learned something new. I decided to share it for anyone interested. The task is to design a variation of the stack data structure but with the additional functionality of fetching the current minimum element in the stack without using more than constant extra space. Try to work it out on your own; I will lay out one of the solutions that I found. If your solution is something else, I would love to know it. Anyway, here it is:

The Idea

Whenever there is a new minimum pushed to the stack, use the old minimum in a way to relate to the new minimum while simultaneously being able to regenerate the old minimum. Here is a clearer representation:

Maintain one extra variable associated with the stack, let it be minEle.

Push(int x):

• Case 1: If the stack is empty, insert x and set minEle = x.
• Case 2: If x >= minEle, simply push x.
• Case 3: If x < minEle (when x is the new minimum), push 2*x - minEle. This is because 2*x - previous_minEle < x is always true. Then, set minEle = x.

Pop():

• Case 1: If stk.top() >= minEle, just pop the topmost element.
• Case 2: If stk.top() < minEle, then we know that this is actually 2*minEle - previous_minEle. Since we know minEle, we can find the previous minEle, update minEle, and then pop the top element.

I have written an implementation in C++ using an object-oriented approach here: MinStack.cpp.

Here is a sample test run: