Maximum Frequency Stack

Maximum Frequency Stack is a classic design problem. It looks intimidating, but it collapses into one neat trick: instead of one stack, keep a separate stack for every frequency level.

The slow way first

The obvious approach: store everything in one list. On each pop, scan the whole structure to find the value with the highest count, breaking ties by position. That works but every pop is O(n), and recomputing counts each time is wasteful.

The question to ask: what do I wish I had precomputed? I wish that, the moment I needed the answer, the most-frequent-and-most-recent value was already sitting on top of a stack — no scan required.

The idea: a stack per frequency

Keep a dictionary group that maps a frequency f to a stack of values that have reached count f. Also track each value's current count in freq, and the overall maxFreq.

When you push(val), its new count f tells you exactly which stack it belongs in: append it to group[f]. When you pop(), the answer is always the top of group[maxFreq] — that value is both the most frequent and, because it is on top, the most recent at that frequency.

The magic: pushing a value to group[f] records the order of arrivals at each frequency level for free. So ties are broken by recency automatically, just by popping from a stack.

Walk through it

Step through the animation. Each push bumps a count in freq, may raise maxFreq, and drops the value into the matching frequency column. Watch the three pops: each one pulls from the top of the highest column, and when a column empties, maxFreq ticks down so the next pop reads the right stack.

Pseudocode

init: freq = {}, group = {}, maxFreq = 0
 
push(val):
    f = freq[val] + 1            # this value's new count
    freq[val] = f
    maxFreq = max(maxFreq, f)
    group[f].push(val)           # append to that frequency's stack
 
pop():
    f = maxFreq
    val = group[f].pop()         # top of the highest-frequency stack
    freq[val] -= 1
    if group[f] is now empty:
        maxFreq -= 1
    return val

The Python solution

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.group = {}
        self.maxFreq = 0
 
    def push(self, val):
        f = self.freq.get(val, 0) + 1
        self.freq[val] = f
        self.maxFreq = max(self.maxFreq, f)
        self.group.setdefault(f, []).append(val)
 
    def pop(self):
        f = self.maxFreq
        val = self.group[f].pop()
        self.freq[val] -= 1
        if not self.group[f]:
            self.maxFreq -= 1
        return val

• freq maps each value to its current count; group maps a count to the stack of values that have hit it.
• In push, f is the value's new count, so group[f] is exactly the right stack to append to.
• maxFreq = max(maxFreq, f) keeps the highest frequency seen so far.
• In pop, we read group[maxFreq] and pop its top — the most frequent, most recent value.
• After popping, if that stack is now empty, maxFreq must drop by one so the next pop looks at the right level.

Complexity

Both operations are O(1). We trade O(n) extra space (the freq map plus the frequency stacks) for constant-time pushes and pops — the same memory-for-speed bargain behind most design problems.

When this pattern shows up

Practice