Auxiliary Stack Tracking

Description

A stack should also report its current minimum in O(1). Scanning is O(n). A single "minimum so far" variable breaks as soon as the minimum is popped - there's no way to know what the minimum was before it arrived. The fix is to remember the answer for every level of the stack.

This skill covers keeping a second stack of answers in step with the main one: the minimum at every level, so push, pop and getMin are all O(1). It also covers the related frequency stack, a stack per count, which pops the most frequent and most recent value in O(1).

We'll go from simple to more technical:

1. The pattern: a min stack with a parallel stack of running minimums.
2. A second flavor: a stack of stacks by frequency (Maximum Frequency Stack).
3. Where per-level state shows up (undo histories, evaluators, frequency-aware caches).
4. What breaks it: drifting stacks, < versus <=, one running variable, encoding overflow.

The approach

Deque<Integer> stack = new ArrayDeque<>(), mins = new ArrayDeque<>();

void push(int val) {
    stack.push(val);
    mins.push(mins.isEmpty() ? val : Math.min(val, mins.peek()));   // minimum of everything up to here
}
void pop()   { stack.pop(); mins.pop(); }       // always together
int top()    { return stack.peek(); }
int getMin() { return mins.peek(); }

stack, mins = [], []


def push(val: int) -> None:
    stack.append(val)
    mins.append(val if not mins else min(val, mins[-1]))   # minimum of everything up to here


def pop() -> None:
    stack.pop()
    mins.pop()                                    # always together


def top() -> int:
    return stack[-1]


def get_min() -> int:
    return mins[-1]

mins has one entry per level: the minimum of the stack from the bottom up to that level. Popping both together "undoes" the minimum along with the value, so every operation is O(1). A common space-saving variant pushes to mins only when the new value is <= the current minimum, and pops mins when the popped value equals its top - the comparison must be <=: with <, pushing 0, 1, 0 and popping once loses the minimum 0 that's still in the stack.

A second flavor: a stack of stacks by frequency

"Pop the most frequent value; on ties, the one pushed most recently." Keep each value's count, and for each count a stack of the values that reached it:

Map<Integer, Integer> freq = new HashMap<>();
Map<Integer, Deque<Integer>> byFreq = new HashMap<>();
int maxFreq = 0;

void push(int val) {
    int f = freq.merge(val, 1, Integer::sum);
    maxFreq = Math.max(maxFreq, f);
    byFreq.computeIfAbsent(f, x -> new ArrayDeque<>()).push(val);
}
int pop() {
    Deque<Integer> top = byFreq.get(maxFreq);
    int val = top.pop();                        // most frequent, most recent among them
    freq.merge(val, -1, Integer::sum);
    if (top.isEmpty()) maxFreq--;
    return val;
}

from collections import defaultdict

freq = defaultdict(int)
by_freq = defaultdict(list)                       # count -> values that reached it, most recent last
max_freq = 0


def push(val: int) -> None:
    global max_freq
    freq[val] += 1
    max_freq = max(max_freq, freq[val])
    by_freq[freq[val]].append(val)


def pop() -> int:
    global max_freq
    top = by_freq[max_freq]
    val = top.pop()                               # most frequent, most recent among them
    freq[val] -= 1
    if not top:
        max_freq -= 1
    return val

A value pushed three times sits in the stacks for counts 1, 2 and 3; popping it from count 3 leaves its earlier copies where they belong. Each stack is ordered by recency, so ties need no extra comparison, and maxFreq drops by exactly one when its stack empties. All O(1).

Where you'll see it

Undo stacks that must report aggregate state (the lowest price in the current edit history, the current indentation depth), expression evaluators that track the running maximum, and caches that evict the most frequently used recent item all keep per-level state beside the main structure.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why can't a single min variable support pop?

2. In the space-saving min stack, why must a new value be pushed to mins when it is <= (not <) the current minimum?

3. How does the frequency stack break ties by recency without comparing anything?

Key takeaways

• Store the aggregate for every level in a parallel stack and pop both together.
• In the space-saving variant, use <= so repeated minimums survive.
• For "most frequent, most recent": a map from count to a stack of values, plus maxFreq.
• Encoded single-stack tricks need a long.