Maximum Frequency Stack

Problem

FreqStack supports push(x) and pop() which removes the most frequently pushed element (most recent if tie).

Key insight: Map frequency → stack of elements at that frequency. Track max_freq. On pop: remove from max_freq bucket, if empty decrement max_freq.

Solutions

// C++
class FreqStack {
    unordered_map<int,int> freq;
    unordered_map<int,stack<int>> group;
    int maxFreq = 0;
public:
    void push(int val) {
        int f = ++freq[val];
        maxFreq = max(maxFreq, f);
        group[f].push(val);
    }
    int pop() {
        int val = group[maxFreq].top(); group[maxFreq].pop();
        freq[val]--;
        if (group[maxFreq].empty()) maxFreq--;
        return val;
    }
};

// Java
class FreqStack {
    Map<Integer,Integer> freq = new HashMap<>();
    Map<Integer,Deque<Integer>> group = new HashMap<>();
    int maxFreq = 0;
    public void push(int val) {
        int f = freq.merge(val, 1, Integer::sum);
        maxFreq = Math.max(maxFreq, f);
        group.computeIfAbsent(f, k->new ArrayDeque<>()).push(val);
    }
    public int pop() {
        int val = group.get(maxFreq).pop();
        freq.merge(val, -1, Integer::sum);
        if (group.get(maxFreq).isEmpty()) maxFreq--;
        return val;
    }
}

// JavaScript
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 val = this.group.get(this.maxFreq).pop();
        this.freq.set(val, this.freq.get(val) - 1);
        if (!this.group.get(this.maxFreq).length) this.maxFreq--;
        return val;
    }
}

# Python
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):
        self.freq[val] += 1
        f = self.freq[val]
        self.max_freq = max(self.max_freq, f)
        self.group[f].append(val)

    def pop(self):
        val = self.group[self.max_freq].pop()
        self.freq[val] -= 1
        if not self.group[self.max_freq]:
            self.max_freq -= 1
        return val

Complexity

push/pop: O(1)
Space: O(n)

Key Insight

Bucket stacks: group[f] = elements pushed when their frequency was exactly f. The top of group[max_freq] is always the most frequent, most recently pushed.