Min Stack

Design a stack with push, pop, top, and getMin, where every operation runs in O(1). The naive idea — track a single min variable — breaks on pop: removing the current minimum loses the previous one.

The key insight: stack LIFO order means the minimum "at the moment each element was pushed" is exactly what you need after pops. Keep a second stack that stores, alongside every element, the minimum of the stack at that point. On push, min_stack gets min(x, current_min); on pop, both stacks pop together. getMin() is then just a peek at the second stack's top. The min stack never grows differently from the main stack, so every op stays O(1).

Approach in steps:

1. push(x): push x; push min(x, min_stack.top) — using +inf as the initial value.
2. pop(): pop both stacks.
3. getMin(): peek the min stack.

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []
 
    def push(self, x):
        self.stack.append(x)
        cur = x if not self.mins else min(x, self.mins[-1])
        self.mins.append(cur)
 
    def pop(self):
        self.stack.pop()
        self.mins.pop()
 
    def top(self):
        return self.stack[-1]
 
    def getMin(self):
        return self.mins[-1]

Time is O(1) for every operation, space O(n).

Trickiest edge case: duplicate minima. push(1), push(1) — popping one 1 must leave getMin() == 1, which works only because the min stack stores a value per element, not a single flag. pop must never touch the stacks when empty; the problem guarantees you only pop existing elements, but the getMin on an empty stack is still undefined.