The Constant Min Stack

Instant Intelligence (O(1))

Retrieving the minimum value from a stack usually requires looking at every element ($O(n)$). However, by using a Dual Stack strategy, we can know the minimum value instantly ($O(1)$) no matter how large the stack grows!

The Assignment

Your mission is to build a high-performance Min-Stack.

1. Maintain two internal arrays: a Data Stack and a Min-Tracking Stack.
2. When pushing a value x:
   • Push x to the Data Stack.
   • Push the current minimum (either x or the top of the Min-Tracking Stack) to the Min-Tracking Stack.
3. Handle these commands:
   • "PUSH": Add the value to both trackers.
   • "POP": Remove the top from both and print the value.
   • "GETMIN": Print the top value of the Min-Tracking Stack.