Min Stack

Signal

"O(1) min/max alongside normal stack operations" means the stack must carry its own running summary — recomputing the min by scanning breaks the O(1) requirement, so each frame needs to remember the min as of that frame.

Approach

Push pairs of (value, min-so-far) instead of bare values. On push, the new min-so-far is min(value, current min). On pop, the previous min is automatically restored because it's baked into the frame beneath — no recomputation needed.

Skeleton

stack = []  # entries: (value, min_so_far)
def push(x):
    new_min = min(x, stack.top.min_so_far) if stack else x
    stack.push((x, new_min))
def pop(): stack.pop()
def top(): return stack.top.value
def get_min(): return stack.top.min_so_far

Solution

class MinStack:
    def __init__(self) -> None:
        self._stack: list[tuple[int, int]] = []

    def push(self, val: int) -> None:
        new_min = min(val, self._stack[-1][1]) if self._stack else val
        self._stack.append((val, new_min))

    def pop(self) -> None:
        self._stack.pop()

    def top(self) -> int:
        return self._stack[-1][0]

    def get_min(self) -> int:
        return self._stack[-1][1]

Complexity

O(1) time for every operation. O(n) space — one extra int per element for the running min.

Pitfalls

• Storing a single global "current min" variable instead of per-frame history breaks on pop: once you pop past the element that was the min, you have no way to recover the previous min without rescanning.
• A tempting "optimization" — only push to a separate min-stack when the new value is <= the current min — still needs a matching pop rule (pop the min-stack only when the popped value equals its top); the pair-per-frame version above avoids that bookkeeping entirely.