Implement a special stack that supports the following operations in constant time:
We can implement the required data structure in many ways.
In this case, we are using O(N) extra space.
1. Use two stacks.
2. One two store the actual items and the other to store minimum so far.
3. When pushing an item, push it in the main stack and if it's smaller than the top of the min stack push in the min stack too. Otherwise push the top of the min stack again.
4. When popping an item, pop from both the stacks.
5. Get min will just read the top of stack from the min stack.