Maximum Frequency Stack [Hard] — Frequency + Group Stacks

Problem Statement

Design FreqStack that:

push(val): Push integer onto stack.
pop(): Remove and return the most frequent element. If tie, return the one closest to the top of the stack.

push 5,7,5,7,4,5 → pop → 5 (freq 3), pop → 7 (freq 2, more recent), ...

Intuition

Maintain:

freq[val] = current frequency of val
group[freq] = stack of elements with that frequency
maxFreq = current max frequency

On push: increment freq, push to group[freq], update maxFreq. On pop: pop from group[maxFreq], decrement freq[val], if group empty decrement maxFreq.

Solutions

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: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        self.max_freq = max(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

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, x->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,vector<int>> group;
    int maxFreq=0;
public:
    void push(int val){int f=++freq[val];maxFreq=max(maxFreq,f);group[f].push_back(val);}
    int pop(){int val=group[maxFreq].back();group[maxFreq].pop_back();freq[val]--;if(group[maxFreq].empty())maxFreq--;return val;}
};

Complexity

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