Maximum Frequency Stack

hard hash map stack design ordered set

Problem

Design FreqStack with push(x) and pop() such that pop returns the most frequent value (ties broken by most-recent push).

Inputpush(5),push(7),push(5),push(7),push(4),push(5),pop()

Output5

Keep a stack per frequency level; pop always reads from the top level.

ops (e.g. push 3; push 1; pop)

from collections import defaultdict
class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)
        self.groups = defaultdict(list)
        self.maxf = 0
    def push(self, x):
        self.freq[x] += 1
        f = self.freq[x]
        if f > self.maxf: self.maxf = f
        self.groups[f].append(x)
    def pop(self):
        x = self.groups[self.maxf].pop()
        self.freq[x] -= 1
        if not self.groups[self.maxf]: self.maxf -= 1
        return x

class FreqStack {
  constructor() { this.freq = new Map(); this.groups = new Map(); this.maxf = 0; }
  push(x) {
    const f = (this.freq.get(x) || 0) + 1;
    this.freq.set(x, f);
    if (f > this.maxf) this.maxf = f;
    if (!this.groups.has(f)) this.groups.set(f, []);
    this.groups.get(f).push(x);
  }
  pop() {
    const top = this.groups.get(this.maxf);
    const x = top.pop();
    this.freq.set(x, this.freq.get(x) - 1);
    if (top.length === 0) this.maxf--;
    return x;
  }
}

class FreqStack {
    Map<Integer, Integer> freq = new HashMap<>();
    Map<Integer, Deque<Integer>> groups = new HashMap<>();
    int maxf = 0;
    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        if (f > maxf) maxf = f;
        groups.computeIfAbsent(f, k -> new ArrayDeque<>()).push(x);
    }
    public int pop() {
        int x = groups.get(maxf).pop();
        freq.put(x, freq.get(x) - 1);
        if (groups.get(maxf).isEmpty()) maxf--;
        return x;
    }
}

class FreqStack {
    unordered_map<int, int> freq;
    unordered_map<int, vector<int>> groups;
    int maxf = 0;
public:
    void push(int x) {
        int f = ++freq[x];
        if (f > maxf) maxf = f;
        groups[f].push_back(x);
    }
    int pop() {
        int x = groups[maxf].back();
        groups[maxf].pop_back();
        freq[x]--;
        if (groups[maxf].empty()) maxf--;
        return x;
    }
};

Explanation

The key insight is to give each frequency level its own little stack. When a value is pushed and reaches frequency f, we drop a copy of it into the sub-stack for level f. Popping then always reads from the highest level, which gives the most frequent value, and being a stack it naturally breaks ties by most recent.

We keep freq (a count per value), groups (a list/stack per frequency), and maxf (the highest frequency seen so far). On push(x) we bump freq[x], update maxf if needed, and append x to groups[freq[x]].

On pop() we take the top of groups[maxf] — that value appears most often, and because we append in push order, the last one in is the most recent. We then lower its count, and if that group becomes empty we drop maxf by one.

Example: pushing 5,7,5,7,4,5 builds level 1 = [5,7,4], level 2 = [5,7], level 3 = [5]. The top level is 3, holding 5, so pop() returns 5.

This works because each push lands in exactly the group matching its new count, so the highest non-empty group always holds a value at the current maximum frequency, with recency handled for free by the sub-stack.

Time: O(1) per op Space: O(n)