min_stack.py

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

Operations:
1. push(x)   -> Push element x onto the stack.
2. pop()     -> Removes the top element from the stack.
3. top()     -> Get the top element.
4. get_min() -> Retrieve the minimum element in the stack.

Example:
    min_stack = MinStack()
    min_stack.push(-2)
    min_stack.push(0)
    min_stack.push(-3)
    print(min_stack.get_min())  # Output: -3
    min_stack.pop()
    print(min_stack.top())      # Output: 0
    print(min_stack.get_min())  # Output: -2

Time Complexity:
- push: O(1)
- pop: O(1)
- top: O(1)
- get_min: O(1)

Space Complexity:
- O(n) extra space for the auxiliary stack
"""


class MinStack:
    def __init__(self):
        """
        Initialize two stacks:
        - main_stack: stores all elements
        - min_stack: stores the current minimum element at each level
        """
        self.main_stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, x: int) -> None:
        """Push element x onto stack."""
        self.main_stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        """Remove the element on top of the stack."""
        if self.main_stack:
            val = self.main_stack.pop()
            if val == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self) -> int | None:
        """Get the top element of the stack."""
        return self.main_stack[-1] if self.main_stack else None

    def get_min(self) -> int | None:
        """Retrieve the minimum element in the stack."""
        return self.min_stack[-1] if self.min_stack else None


# Example usage
if __name__ == "__main__":
    min_stack = MinStack()
    min_stack.push(-2)
    min_stack.push(0)
    min_stack.push(-3)
    print("Current Min:", min_stack.get_min())  # Output: -3
    min_stack.pop()
    print("Top Element:", min_stack.top())  # Output: 0
    print("Current Min:", min_stack.get_min())  # Output: -2