Maximum Frequency Stack — Bucket-per-Frequency Design

Problem 294 · Maximum Frequency Stack

Difficulty: Hard · Pattern: Frequency Buckets + HashMap

Push values; pop the most frequently seen value (ties broken by most recently pushed).

Intuition

Maintain:

freq map: element -> current frequency
group map: freq -> stack of elements at that freq
maxfreq counter

On pop: pop from group[maxfreq]; if that group becomes empty, decrement maxfreq.

Solutions

# Python
from collections import defaultdict
class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)
        self.group = defaultdict(list)
        self.maxfreq = 0

    def push(self, val):
        self.freq[val] += 1
        f = self.freq[val]
        self.maxfreq = max(self.maxfreq, f)
        self.group[f].append(val)

    def pop(self):
        val = self.group[self.maxfreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        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;
    }
}

// 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;
    }
};

Complexity

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