Max Frequency Stack — Stack of Stacks Indexed by Frequency

Problem Statement#

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

• FreqStack() constructs an empty frequency stack.
• void push(int val) pushes an integer val onto the top of the stack.
• int pop() removes and returns the most frequent element in the stack.
  • If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

Constraints:

• 0 <= val <= 10^9
• At most 2 * 10^4 calls in total.
• It is guaranteed that pop is called only on a non-empty stack.

FreqStack s;
s.push(5); s.push(7); s.push(5); s.push(7); s.push(4); s.push(5);
s.pop();  // 5 (count 3)
s.pop();  // 7 (count 2, more recent than 5 with count 2)
s.pop();  // 5
s.pop();  // 4

Why This Problem Matters#

LeetCode 895 Maximum Frequency Stack is one of the most elegant FAANG hard data structure design problems and shows up at Amazon, Google, Meta, and Bloomberg. The naive solutions either use a heap (O(log n) per pop) or a hash map plus full scan (O(n) per pop). The optimal solution uses a stack-of-stacks layered by frequency — O(1) push and pop, no heap, no scans.

Recruiters use this problem to confirm that you can design custom data structures by composing two simpler primitives (a hash map for counts and an array of stacks for frequency layers). It is a perfect "data structure synthesis" exercise and a strong hire signal when solved cleanly.

The Core Insight#

For each value v, track its current frequency in a hash map freq. We also maintain an array of stacks called groups, where groups[f] is a stack of all values that have ever reached frequency f at some push.

On push(v):

• Increment freq[v]; let f equal freq[v].
• Push v onto groups[f]. (Append a new layer if f exceeds groups length.)
• Update maxFreq if f exceeds it.

On pop:

• Pop from groups[maxFreq]; that is the most frequent and most recent value.
• Decrement freq[v].
• If groups[maxFreq] is now empty, decrement maxFreq.

The crucial insight is that when we push v with new frequency f, we do not remove v from groups[f minus 1]. The value is conceptually on every layer it has reached. When we pop from layer f, we are removing v's "presence" at frequency f, leaving its presence at frequency f minus 1 intact for future pops. This perfectly captures both the frequency-priority and tie-breaking-by-recency semantics.

Visual Dry Run#

Sequence: push(5), push(7), push(5), push(7), push(4), push(5).

Now pop. groups[2] is [5]; pop returns 5. freq[5] becomes 2. groups[2] empty, maxFreq drops to 2. Pop. groups[1] (zero-indexed as groups[2-1]=groups[1]) is [5,7]; pop returns 7. freq[7] becomes 1. groups[1] still has [5]. Pop. groups[1] is [5]; pop returns 5. freq[5] becomes 1. groups[1] empty, maxFreq drops to 1. Pop. groups[0] is [5,7,4]; pop returns 4.

Final pop sequence: 5, 7, 5, 4 — matches expected output.

Solution (Optimal)#

from collections import defaultdict
from typing import List, Dict
 
class FreqStack:
    def __init__(self):
        self.freq: Dict[int, int] = defaultdict(int)
        self.groups: List[List[int]] = []  # groups[f] is the stack at frequency f+1
        self.max_freq = 0
 
    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        if f > len(self.groups):
            self.groups.append([])
        self.groups[f - 1].append(val)
        if f > self.max_freq:
            self.max_freq = f
 
    def pop(self) -> int:
        v = self.groups[self.max_freq - 1].pop()
        self.freq[v] -= 1
        if not self.groups[self.max_freq - 1]:
            self.groups.pop()
            self.max_freq -= 1
        return v

class FreqStack {
  constructor() {
    this.freq = new Map();
    this.groups = []; // groups[f] is stack at frequency f+1
    this.maxFreq = 0;
  }
  push(val) {
    const f = (this.freq.get(val) || 0) + 1;
    this.freq.set(val, f);
    if (f > this.groups.length) this.groups.push([]);
    this.groups[f - 1].push(val);
    if (f > this.maxFreq) this.maxFreq = f;
  }
  pop() {
    const top = this.groups[this.maxFreq - 1];
    const v = top.pop();
    this.freq.set(v, this.freq.get(v) - 1);
    if (top.length === 0) {
      this.groups.pop();
      this.maxFreq--;
    }
    return v;
  }
}

Complexity. push and pop are both O(1). Space O(n) for n total pushes — each push contributes one entry to one group.

Common Mistakes#

• Using a max-heap of (frequency, push-index, value) tuples. It works in O(log n) per op but is more complex and slower.
• Removing v from lower-frequency groups when re-pushing. This breaks tie-breaking — you must leave v's previous-frequency presences intact.
• Forgetting to decrement maxFreq when the top group empties. Subsequent pops will fail or return the wrong value.
• Using a Python dict without defaultdict and getting KeyError on the first push of a new value.
• Storing values inside groups as their own metadata (timestamp etc.); only the value is needed because the layer index already encodes frequency.

Interview Tips#

• Begin by sketching a heap-based solution and stating its O(log n) cost. Then introduce the stack-of-stacks for O(1).
• Walk through the dry run to make the "value lives on every layer" semantics concrete.
• Articulate the invariant clearly: groups[f-1] is a stack of values in push order that ever reached frequency f.
• Discuss the tie-breaking. The latest push of a tying frequency lands on top of the appropriate group, so pop naturally returns the most recent.
• Mention the production analogue: priority caches with frequency-based eviction.

Follow-up Questions#

1. What if you must support get-min-frequency element instead? Track minFreq with similar logic and add a min-aware pop.
2. What if values are removed from arbitrary layers (not just the top)? Lazy deletion or a doubly linked list per layer.
3. What if frequencies must be reset after a pop? That changes the semantics significantly; consider a counting Bloom filter or generational counters.
4. How would you persist this structure to disk? Serialize groups and freq maps; rebuild maxFreq on load.
5. What if values are unbounded big integers? Use a hash map keyed by integer; complexity unchanged.

Key Takeaways#

• A stack-of-stacks indexed by frequency gives O(1) push and pop.
• Each value lives on every layer it has reached — do not remove from lower layers.
• The maxFreq counter tracks the active top group; decrement when that group empties.
• Tie-breaking by recency falls out automatically from the stack semantics within each group.
• This composition pattern (hash map plus array of stacks) is reusable for many frequency-aware structures.
• Strictly better than heap solutions: O(1) versus O(log n) per operation.