08. Maximum Frequency Stack (FreqStack)

Difficulty:HardPattern:Frequency Map Stack BucketTime:O(1) Push / PopSpace:O(n)

Design a stack-like data structure that pushes and pops elements, where pop removes and returns the most frequent element in the stack. If there is a tie, the element closest to the top of the stack is popped.

How It Works & Algorithmic Design

Solves using Hash Map Frequency Counters + Stack Map Buckets:

Freq Map: freqMap[val] stores element frequencies.
Group Map: groupMap[freq] stores stack of elements sharing exact frequency freq.
Max Frequency Track: Maintain integer maxFreq.
Operations:
- push(val): Increment freqMap[val], update maxFreq = Math.max(maxFreq, freq), push val to groupMap[freq].
- pop(): Pop element x from groupMap[maxFreq]. Decrement freqMap[x]. If groupMap[maxFreq] becomes empty, decrement maxFreq--. Return x.

Why This Approach Works Best

Grouping elements by frequency stack buckets achieves $O(1)$ constant time for both push and pop operations.

Example Walkthrough

Operations: push(5), push(7), push(5), push(7), push(4), push(5), pop()

FreqStack calls.

Frequency State: 5 has freq 3 (most frequent).

Pops 5.

Output: 5

Popped most frequent element.

Answer: FreqStack implementation

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);
    this.maxFreq = Math.max(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--;
    return val;
  }
}

💡 Group elements in stack buckets indexed by frequency count for constant O(1) pops.

Key Takeaways

Maintains frequency mapping alongside stack bucket structures.
Tie breaking defaults automatically to LIFO order inside frequency stacks.
All operations execute in constant $O(1)$ time.