Min Stack Implementation

On this New Year's Eve, as you prepare to wipe out the old and welcome new beginnings, imagine setting up a system to track your daily resolutions. In this problem, you need to implement a Min Stack—a stack that, in addition to typical stack operations, can also retrieve the minimum element in constant time.

Problem Description

Design a stack that supports the following operations in constant time:

• push(val): Push an element 'val' onto the stack.
• pop(): Remove the element on top of the stack and return it.
• top(): Get the top element.
• getMin(): Retrieve the minimum element in the stack.

Your solution should be efficient and work for any sequence of operations. This problem tests your understanding of stack usage and managing additional state within the stack.

Example:

MinStack stack = new MinStack();
stack.push(-2);
stack.push(0);
stack.push(-3);

stack.getMin();   // Returns -3
stack.pop();
stack.top();      // Returns 0
stack.getMin();   // Returns -2

You may assume that all operations are valid (for example, pop or top will never be called on an empty stack).

Now, implement your solution using the starter code provided below. Happy coding and Happy New Year!