min_stack.py

class MinStack:
    """LeetCode #155 - Min Stack (Medium)
    https://leetcode.com/problems/min-stack/

    Design a stack supporting push, pop, top and getMin - each in O(1).

    Key insight: getMin cannot scan the stack (that would be O(n)), and a single
    "current minimum" variable is not enough either, because popping the minimum
    must restore the *previous* one. The fix is to remember, for every element,
    what the minimum was at the moment it was pushed. Then popping automatically
    rolls the minimum back.

    Space: O(n) - a second stack of the same height. The classic trade: extra
    memory bought us O(1) time on every operation.
    """

    def __init__(self):
        self.stack = []       # the actual values
        self.mins = []        # mins[i] = minimum among stack[0..i]

    def push(self, val: int) -> None:
        """O(1) - store the value and the running minimum next to it."""
        self.stack.append(val)
        # '<=' rather than '<' also works with a "push only smaller" variant,
        # but storing a min for *every* element keeps both stacks the same
        # height, so pop() stays a simple two-liner.
        current_min = val if not self.mins else min(val, self.mins[-1])
        self.mins.append(current_min)

    def pop(self) -> None:
        """O(1) - drop the value and the minimum that belonged to it."""
        self.stack.pop()
        self.mins.pop()

    def top(self) -> int:
        """O(1) - last pushed value."""
        return self.stack[-1]

    def getMin(self) -> int:
        """O(1) - minimum over everything currently on the stack."""
        return self.mins[-1]