Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?

I found that this question had been asked in Amazon and Bloomberg interviews.

Initially I thought of using an extra min-heap to store the elements. Although this enables us to retrieve the minimum element in O(1), push and pop operations both operates in O(lg N), where N is the total number of elements in the stack. Definitely not a desirable method.

How about recording the current minimum in the stack? This works until you pop current minimum off the stack, where you would have to update your next minimum, which takes O(N) time to examine all elements.

Assume you have an extra stack. What would you do with the extra stack?

Stack is a last in, first out (LIFO) data structure. It can be easily implemented either through an array or a linked list.


Solution:

1st Solution

You can implement this by having each node in the stack keep track of the minimum beneath
itself. Then, to find the min, you just look at what the top element thinks is the min.
When you push an element onto the stack, the element is given the current minimum. It sets its “local min” to be the min.

public class StackWithMin extends Stack {
public void push(int value) {
int newMin = Math.min(value, min());
super.push(new NodeWithMin(value, newMin));
}

public int min() {
if (this.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return peek().min;
}
}
}
class NodeWithMin {
public int value;
public int min;
public NodeWithMin(int v, int min){
value = v;
this.min = min;
}
}
There’s just one issue with this: if we have a large stack, we waste a lot of space by keeping track of the min for every single element.


2nd solution


The solution is surprisingly simple and elegant — Use an extra stack to maintain the minimums. What does this mean?

* To retrieve the current minimum, just return the top element from minimum stack.
* Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too.
* When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.


struct StackGetMin {
void push(int x) {
elements.push(x);
if (minStack.empty() || x <= minStack.top())
minStack.push(x);
}
bool pop() {
if (elements.empty()) return false;
if (elements.top() == minStack.top())
minStack.pop();
elements.pop();
return true;
}
bool getMin(int &min) {
if (minStack.empty()) {
return false;
} else {
min = minStack.top();
return true;
}
}
stack elements;
stack minStack;
};