LeetCode #155 - Min Stack

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

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.**

Another designing stack question - another version of the painful tricky Implementing queue from stack problem. The major difference here is that the stack will possess all functions like a normal stack - push, pop, top (peek), except that there must be another data structure to store and update the minimum value of the whole stack, and return it when getMin() is called.

My initial approach was rather focused on getMin(), in which I would dynamically change the position of elements in the main stack to make sure they are in ascending order from the top down. However, this approach will prove problematic and complicated regarding other operations.

So let's get started.

First, I initialize two empty stacks. The main stack is minStack, and the supplementary stack storing min value is stack (please excuse the naming).

Push

Since minStack acts like a normal stack, we simply push the element to minStack. With stack, we only add the element whenever it is less than stack's top element. This way, we can make sure that stack's top is always the current minimum element of the minStack.

Pop

Again, simply pop the head of minStack. If that value is equal to the head of stack, we pop the head of stack as well.

Top

Simply return the head of minStack, in which I use Stack.peek() operation. stack is not touched in this operation.

getMin

After tons of new additions and removal from our main stack, we are guaranteed that only smaller elements are added to stack. Therefore, return stack's head element.