Implement a Min Stack

To implement a Min Stack with O(1) access to the minimum element, I would utilize a dual-stack approach. We need one primary stack to store all incoming elements and a secondary auxiliary stack dedicated solely to tracking the minimum values. When we perform a push operation, we add the new element to our primary stack. Simultaneously, we check the top of our auxiliary stack. If the auxiliary stack is empty or the new element is less than or equal to the current minimum, we push this new element onto the auxiliary stack as well. This ensures the top of the auxiliary stack always holds the smallest value seen so far. For the pop operation, we remove the top element from the primary stack. Crucially, if this removed element matches the top of the auxiliary stack, we also pop from the auxiliary stack to maintain synchronization. The top and getMin operations simply return the tops of their respective stacks. This design guarantees that every operation runs in constant time because we are only performing basic stack pushes and pops without iteration. While this uses O(n) extra space in the worst case where inputs are sorted in descending order, it strictly adheres to the time constraint required for high-performance applications typical at Apple.