Create a new stack like data structure with Push, Pop and Get Min that runs in O(1).
Solution
The key to solving this problem is what kind of data structure we shall use in the stack class to compute the min in linear time.
For this the best approach is to use another stack called MinStack which will keep track of all the minimum elements of the array in their size order.
Basically we keep checking if the min stack has the least element at the top and if we we encounter a new min we just keep pushing to the top of the list on the minstack
public class MinStack {
private Stack<int> stack;
private Stack<int> minStack;
public MinStack() {
stack = new Stack<int>();
minStack = new Stack<int>();
}
public void Push(int val) {
stack.Push(val);
if (minStack.Count == 0 || val <= minStack.Peek()) {
minStack.Push(val);
}
}
public void Pop() {
if (stack.Count == 0) return;
int popped = stack.Pop();
if (popped == minStack.Peek()) {
minStack.Pop();
}
}
public int Top() {
if (stack.Count == 0) throw new InvalidOperationException("Stack is empty");
return stack.Peek();
}
public int GetMin() {
if (minStack.Count == 0) throw new InvalidOperationException("Stack is empty");
return minStack.Peek();
}
}