Algorithm

Min Stack

Design Pattern

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.

CONSTRAINTS
  • -2³¹ <= val <= 2³¹ - 1
  • pop, top and getMin are always called on a non-empty stack
  • At most 3 × 10⁴ calls will be made to push, pop, top, and getMin
EXAMPLE 1
Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: -3, 0, -2
Push -2 (min=-2), push 0 (min=-2), push -3 (min=-3). getMin()=-3. Pop -3. top()=0. getMin()=-2 (reverts to previous min).
EXAMPLE 2
Input: push(1), push(2), getMin(), pop(), getMin()
Output: 1, 1
Both getMin calls return 1 because 2 is never the minimum.
EXAMPLE 3
Input: push(0), push(1), push(0), getMin(), pop(), getMin()
Output: 0, 0
Duplicate minimum: push 0 twice. After popping one 0, getMin still returns 0 because the first 0 remains.

A stack is naturally great at keeping track of the order of elements. But a standard stack has a secret weakness: it is blind to its own contents. If you want to find the smallest number in a stack of a million items, you have to pop everything out to see them, which destroys the stack and takes O(N) time.

The Search Bottleneck

In a regular stack, the minimum is "somewhere inside." To find it without destroying the stack, you'd have to iterate through the entire underlying array. This makes getMin() an O(N) operation. We need to make it O(1).

The "Time-Traveling" Minimum

The key insight is that for any element at position i, the minimum value in the stack at the moment that element was pushed will never change as long as that element is the top.

Think of it like a Time-Traveler's Log:
1. Every time you push a value onto the main stack, you record the "current champion" (the minimum of the whole stack) in a separate auxiliary stack.
2. The auxiliary stack keeps a history of the minimum value for every single state of the main stack.

Synchronized Dancing

The two stacks must stay perfectly in sync:
- Push: When a new value arrives, compare it to the current top of the minStack. Push the smaller of the two onto the minStack.
- Pop: When a value is removed from the main stack, its corresponding "minimum at that time" must also be removed from the minStack.
- GetMin: Simply look at the top of the minStack.

Optimal Strategy

1. Maintain two stacks: stack and minStack.
2. Push(x):
- stack.push(x)
- minStack.push(min(x, minStack.top() or infinity))
3. Pop():
- stack.pop()
- minStack.pop()
4. GetMin(): Return minStack.top().

python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int):
        self.stack.append(val)
        # Current min is the smaller of val and previous top
        curr_min = val
        if self.min_stack:
            curr_min = min(val, self.min_stack[-1])
        self.min_stack.append(curr_min)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()
Worked Example:watch the min resurface, including a duplicate
0
2
Top
push(2): Main stack = [2]. Min stack tracking running minimums = [2]. getMin() returns 2.
0
2
1
0
Top
push(0): Main stack = [2, 0]. Min stack = [2, 0]. New min 0 is pushed onto min stack. getMin() returns 0.
0
2
1
0
2
3
Top
push(3): Main stack = [2, 0, 3]. Min stack = [2, 0, 0] (3 is larger than 0, so 0 remains the min). getMin() returns 0.
0
2
1
0
2
3
3
0
Top
push(0): Main stack = [2, 0, 3, 0]. Min stack = [2, 0, 0, 0]. Duplicate minimum is pushed. getMin() returns 0.
0
2
1
0
2
3
Top
pop(): Both stacks popped. Main stack = [2, 0, 3]. Min stack = [2, 0, 0]. getMin() still returns 0.
0
2
1
0
Top
pop(): Main stack = [2, 0]. Min stack = [2, 0]. The 3 was popped, min is still 0.
Interactive Strategy Visualization
MIN STACK ARCHITECTURE

Synchronized dual-stack mechanism

DATA STACK
MIN STACK

Mental Model

  • Why Two Stacks? One stack stores the actual elements. The other stores the "minimum at each state".
  • Consistency: Whenever you pop an element that is the current minimum, you must also pop from the min stack.
LOGICSTEP 1/7
Design a stack that retrieves the minimum in O(1).
STRATEGY

Alternative Implementation

You can also use a single stack that stores pairs of `[value, min_so_far]`. This keeps the same logic but avoids managing two separate data structures.

O(N) Scan Every getMin
→
O(1) All Ops · Parallel Min-Stack