Maximum Frequency Stack — FAANG Frequency Map and Group Stacks Design

Problem Statement#

Design a FreqStack that supports push(val) and pop(), where pop() removes and returns the most frequent element. If multiple elements tie for the maximum frequency, return the one pushed most recently.

Constraints:

• 0 <= val <= 10^9
• Up to 2 * 10^4 calls combined to push and pop
• pop is never called on an empty stack

Operations: push(5), push(7), push(5), push(7), push(4), push(5)
pop() -> 5  (only element at freq 3)
pop() -> 7  (5 and 7 share freq 2; 7 was pushed later)
pop() -> 5  (freq 2 group leaves only 5)
pop() -> 4  (freq 1 group; 4 was pushed last at this tier)

Why This Problem Matters#

LeetCode 895 is a Hard-tier favourite at Apple, Google, Amazon, and Uber. Interviewers use it to test whether you can compose multiple data structures into a single coherent API. The naive approach scans every element on each pop in O(n). The interesting design upgrades that to O(1) per operation.

What is being assessed:

• Can you spot that one map alone or one stack alone cannot answer "most frequent and most recent" in O(1)?
• Do you understand invariant maintenance — keeping auxiliary state correct on every mutation so the next call needs no scanning?
• Can you handle tie-breaking, decrementing the running maximum cleanly, and edge cases like the same value pushed many times?

The Core Insight#

Instead of asking which element has the highest frequency at pop time, precompute the answer by bucketing elements by their current frequency.

Three components keep the answer ready in O(1):

1. freq[val] — current push count for each value
2. group[f] — a stack of all values that have ever reached frequency f
3. maxFreq — the highest occupied frequency tier

When you push val, its frequency moves from f-1 to f. The new entry is appended to group[f]. The old entry in group[f-1] is left untouched. So a value pushed three times has entries in group[1], group[2], and group[3]. Within each tier, the stack order naturally encodes recency.

When you pop, the answer is always the top of group[maxFreq]. After popping, if that tier becomes empty, decrement maxFreq by exactly one — never more, since adjacent tiers are always populated together.

Visual Dry Run#

Solution (Optimal)#

from collections import defaultdict
 
class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)
        self.group = 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.group[f].append(val)
 
    def pop(self) -> int:
        val = self.group[self.max_freq].pop()
        self.freq[val] -= 1
        if not self.group[self.max_freq]:
            self.max_freq -= 1
        return val

class FreqStack {
    constructor() {
        this.freq = new Map();
        this.group = 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.group.has(f)) this.group.set(f, []);
        this.group.get(f).push(val);
    }
 
    pop() {
        const stack = this.group.get(this.maxFreq);
        const val = stack.pop();
        this.freq.set(val, this.freq.get(val) - 1);
        if (stack.length === 0) this.maxFreq -= 1;
        return val;
    }
}

Time: O(1) amortised per push and pop Space: O(n) where n is total pushes

Common Mistakes#

• Treating each value as belonging to a single tier and trying to move it during a push — the correct model is additive, the lower tier entry stays.
• Decrementing maxFreq on every pop without checking whether the current tier is empty.
• Using a set or shuffled list for the group bucket, which destroys recency order.
• In JavaScript, calling shift instead of pop on the group array, breaking LIFO behaviour.
• Deleting freq[val] when it reaches zero, which can throw on the next push of the same value.

Interview Tips#

• Walk through the example before writing code so the interviewer sees the bucket-by-frequency intuition.
• Call out the invariants out loud: maxFreq monotonic per push, decrement only when the top tier empties.
• Acknowledge that group can store values across many tiers — this is the magic that keeps pop O(1).
• Note the symmetry with LFU Cache (LeetCode 460) which uses the same structure with a min frequency variable.

Follow-up Questions#

• Add peek returning the same value without mutating state.
• Support getFrequency(val) returning the current count.
• Make it thread-safe for concurrent push and pop.
• Allow weighted pushes where each push of val contributes weight w instead of 1.
• Implement a least-frequent variant — this is the LFU Cache problem.

Key Takeaways#

• Bucket values by frequency to precompute the answer to pop in O(1).
• The same value occupies entries across every frequency tier it has reached, never moved or deleted.
• maxFreq is monotonic on push and decrements by exactly one when its tier empties.
• The group map at any tier is a stack so recency tie-breaking comes for free.
• Pattern generalises to LFU Cache, top-k frequent, and reorganise-string style problems.
• Time per operation is O(1) amortised; total space is O(n) entries across all tiers.
• Invariant-driven design beats search-on-demand — maintain state, do not scan it.