LeetCode 155 Min Stack - Example and Complexity Analysis

Trace: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin().

Push -2: stack = [(-2, -2)]. Value and min both -2.

Push 0: min(0, -2) = -2. Stack = [(-2, -2), (0, -2)].

Push -3: min(-3, -2) = -3. Stack = [(-2, -2), (0, -2), (-3, -3)].

getMin(): return -3.

Pop: remove (-3, -3). Stack = [(-2, -2), (0, -2)].

Top: return 0.

getMin(): return -2 (from remaining top entry).

Each operation touches only the top. $O(1)$ time for all operations. Store two values per element. $O(n)$ space.