Min Stack: Efficiently Track the Minimum Element

We often need data structures that can store a collection of elements and perform common operations like adding new elements and retrieving them. Sometimes, we also require the ability to efficiently find the smallest element currently present in the collection. This challenge focuses on designing a stack-like data structure that supports standard stack operations along with a highly efficient way to retrieve the minimum element at any given time.

Problem Description

You are tasked with implementing a MinStack data structure. This structure should behave like a standard stack, supporting the following operations:

1. push(value): Adds an element value to the top of the stack.
2. pop(): Removes and returns the element at the top of the stack.
3. top(): Returns the element at the top of the stack without removing it.
4. getMin(): Retrieves the minimum element currently in the stack.

The key requirement is that all of these operations, especially getMin(), must be performable in constant time (O(1)).

Expected Behavior:

• push should add an element.
• pop should remove the top element. If the stack is empty, pop might raise an error or return a special value (specify behavior if needed, but for this challenge, assume valid operations).
• top should return the top element. If the stack is empty, it might raise an error or return a special value.
• getMin should return the smallest element among all elements currently in the stack. If the stack is empty, it might raise an error or return a special value.

Edge Cases to Consider:

• An empty stack: What happens when pop, top, or getMin is called on an empty stack?
• Duplicate minimum values: How does the getMin operation behave if there are multiple occurrences of the minimum value?
• Pushing and popping values that change the minimum: The getMin value must always reflect the current minimum.

Examples

Example 1:

Operations:
minStack = new MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.getMin() // returns -3
minStack.pop()
minStack.top()    // returns 0
minStack.getMin() // returns -2

Explanation:

1. push(-2): Stack: [-2]. Min: -2.
2. push(0): Stack: [-2, 0]. Min: -2.
3. push(-3): Stack: [-2, 0, -3]. Min: -3.
4. getMin(): Returns -3.
5. pop(): Removes -3. Stack: [-2, 0].
6. top(): Returns 0.
7. getMin(): The minimum is now -2.

Example 2:

Operations:
minStack = new MinStack()
minStack.push(5)
minStack.push(2)
minStack.push(7)
minStack.getMin() // returns 2
minStack.push(2)
minStack.getMin() // returns 2
minStack.pop()
minStack.getMin() // returns 2
minStack.pop()
minStack.getMin() // returns 5

Explanation:

1. push(5): Stack: [5]. Min: 5.
2. push(2): Stack: [5, 2]. Min: 2.
3. push(7): Stack: [5, 2, 7]. Min: 2.
4. getMin(): Returns 2.
5. push(2): Stack: [5, 2, 7, 2]. Min: 2.
6. getMin(): Returns 2.
7. pop(): Removes 2. Stack: [5, 2, 7]. Min: 2.
8. getMin(): Returns 2.
9. pop(): Removes 7. Stack: [5, 2]. Min: 2.
10. getMin(): Returns 2. (Correction: After popping 7, the stack is [5, 2]. The minimum is still 2. The example explanation needs correction for the last pop. If we pop again, the stack becomes [5] and the min becomes 5.)

Self-correction based on Example 2's expected behavior: The getMin() after popping 7 should correctly return 2, as 2 is still in the stack. The final getMin() should indeed return 5 after the next pop removes 2.

Example 3 (Empty Stack Behavior - assumed):

Operations:
minStack = new MinStack()
minStack.getMin() // Assume returns null or raises an error
minStack.pop()    // Assume returns null or raises an error
minStack.top()    // Assume returns null or raises an error

Explanation: When operations are called on an empty stack, the system should handle this gracefully, for example, by returning a designated value (like null or undefined) or by raising an appropriate exception. For the purpose of this challenge, you can assume calls to pop, top, and getMin will only occur on non-empty stacks, or define your preferred error handling.

Constraints

• The number of operations (push, pop, top, getMin) will be between 1 and 10,000.
• The values pushed onto the stack will be integers between -2³¹ and 2³¹ - 1.
• All operations must be completed in O(1) time complexity. This means the time taken for each operation should not depend on the number of elements in the stack.

Notes

• Consider how you will store elements such that you can always retrieve the minimum in constant time.
• Simply iterating through the stack to find the minimum for getMin() will not meet the O(1) time complexity requirement.
• You are allowed to use auxiliary data structures if they help achieve the O(1) time complexity for all operations.
• The specific return type for pop, top, and getMin on an empty stack is up to your implementation, but clarity and consistency are important. For testing purposes, assume valid operation sequences or handle empty stack scenarios as described.