Design a stack that supports push, pop, top, and get minimum. Every operation must run in constant time.
DSA Animator › DSA Revision › Stack › Min Stack
Remember: store the minimum at every level. Then pops can never lose the previous minimum. The video solves Min Stack (LeetCode 155, Medium) with the Stack Design pattern from the Stack topic, and you can replay every step in the interactive Min Stack animation.
Design a stack that supports push, pop, top, and get minimum. Every operation must run in constant time.
Push minus 2, push 0, push minus 3, and get min returns minus 3. Then pop, top returns 0, and get min returns minus 2.
Scanning the whole stack for the minimum is O of n per call. Keeping one minimum variable breaks after a pop, because you lose the previous minimum.
Keep a second stack of minimums, the same height as the main stack. Each entry is the minimum of everything at or below that level. Push and pop both stacks together, and the minimum is always on top.
Push minus 2: the min stack holds minus 2. Push 0: the minimum is still minus 2, so push minus 2 again. Push minus 3: the new minimum is minus 3. Get min reads the top: minus 3. Pop removes minus 3 from both stacks. Top returns 0, and get min now returns minus 2.
In code, push pushes the value, and the smaller of the value and the current minimum. Pop pops both stacks. Top reads the main stack, and get min reads the min stack. Every operation is O of 1 time, with O of n extra space.
Remember: store the minimum at every level. Then pops can never lose the previous minimum.