Minimum stack

Problem: Design a stack that supports push, pop, and retrieving the minimum element in constant time.

Algo:
1. Maintain one more stack to store minimum elements (minimum stack).
2. To retrieve the current minimum, just return the top element from minimum stack.
3. 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.
4. 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.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

void push(int x) {   stack.push(x);   if (minStack.empty() || x <= minStack.top()) {     minStack.push(x);   } }   int pop() {   if (stack.empty()) return -1;   if (elements.top() == minStack.top()) {     minStack.pop();   }   return stack.pop();    }   int getMin() {   if (minStack.empty()) {     return -1;   } else {     return minStack.top();        } }