Maximum Frequency Stack — Frequency Buckets Interview Design

Problem Statement#

Design a stack with two operations:

• push(val) — add to the stack.
• pop() — remove and return the most frequent value. On ties, return the value closest to the top of the stack.

Constraints:

• 0 <= val <= 10^9
• At most 2 * 10^4 calls.
• pop is only called when stack is non-empty.

Input:
push(5), push(7), push(5), push(7), push(4), push(5)
pop(), pop(), pop(), pop()
Output: 5, 7, 5, 4

Input:
push(1), push(1), pop()
Output: 1

Why This Problem Matters#

LeetCode 895 is an Amazon, Google, and Meta hard design interview problem. While the obvious approach is a max-heap with (freq, push_index, val), the elegant O(1) solution uses frequency-bucket stacks — a pattern that elegantly handles tiebreaks by recency.

This is one of the most asked priority queue interview design questions because it forces you to look beyond the heap. The bucket-stack idea also appears in LFU Cache and other frequency-aware designs.

The Core Insight#

Maintain freq as a map from value to its current count, and stacks as a map from frequency to a stack of values that have reached that frequency. On push of v, increment freq[v] to f and append v to stacks[f]. On pop, take from stacks[max_freq], decrement counts, and update max_freq.

Visual Dry Run#

push 5,7,5,7,4,5

Solution (Optimal)#

from collections import defaultdict
 
class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)
        self.stacks = defaultdict(list)
        self.max_freq = 0
 
    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        if f > self.max_freq:
            self.max_freq = f
        self.stacks[f].append(val)
 
    def pop(self) -> int:
        v = self.stacks[self.max_freq].pop()
        self.freq[v] -= 1
        if not self.stacks[self.max_freq]:
            self.max_freq -= 1
        return v

class FreqStack {
    constructor() {
        this.freq = new Map();
        this.stacks = new Map();
        this.maxFreq = 0;
    }
    push(val) {
        const f = (this.freq.get(val) || 0) + 1;
        this.freq.set(val, f);
        if (f > this.maxFreq) this.maxFreq = f;
        if (!this.stacks.has(f)) this.stacks.set(f, []);
        this.stacks.get(f).push(val);
    }
    pop() {
        const stack = this.stacks.get(this.maxFreq);
        const v = stack.pop();
        this.freq.set(v, this.freq.get(v) - 1);
        if (stack.length === 0) {
            this.stacks.delete(this.maxFreq);
            this.maxFreq--;
        }
        return v;
    }
}

Time: O(1) for push and pop, amortized. Space: O(N) — total entries across all stacks equal total pushes.

Common Mistakes#

• Using a single max-heap with (freq, ts, val) works but is O(log N), not O(1).
• Forgetting that the same value appears in multiple frequency stacks (one per frequency level).
• Treating it as a regular stack and counting on each pop — O(N) per pop.
• Not decrementing max_freq when its bucket empties.
• Using a counter without preserving push order in tiebreaks.

Interview Tips#

• Walk through the bucket-stack analogy: each frequency tier is its own LIFO timeline.
• Compare with the max-heap approach and explain why the bucket version is strictly better.
• Connect to LFU Cache as a related design pattern.
• Discuss thread safety briefly if the interviewer cares about real systems.

Follow-up Questions#

• Add peek() without modifying state. Hint: read stacks[max_freq][-1].
• What if there is a memory cap on stacks? Hint: bound history per bucket; need eviction policy.
• Add decrement(val) operation. Hint: tricky — might need to find val in current bucket.
• How would you persist this across processes? Hint: serialize freq map and per-bucket lists.
• Implement with a heap version for comparison. Hint: max-heap of (freq, push_index, val).

Key Takeaways#

• LeetCode 895 Maximum Frequency Stack achieves O(1) push and pop with frequency-bucket stacks.
• The same value can appear in multiple stacks — one per frequency level it has reached.
• max_freq only ever changes by plus or minus one.
• A max-heap also works but is O(log N) per op.
• The bucket-stack pattern reuses for LFU Cache.
• Time: O(1) amortized. Space: O(N total entries).
• A favorite Amazon, Google, and Meta priority queue interview design problem.