Managing Frequencies with Hash Maps (Increment, Decrement, Prune)

Managing frequency means coordinated increment/decrement, lazy deletion, and occasionally min-heap keyed by frequency when you must always know the rarest active element.

Why this shows up in the real world

LFU cache tracks usage counts; task schedulers demote hot queues when fairness requires boosting cold ones.

Core idea (explained for students)

Invariant checklist: every + has matching - on eviction paths; when count goes 0 remove key to keep len(d) meaningful; heap stores (freq, key) with lazy deletes.

Try this in Python

from collections import defaultdict


class FreqManager:
    def __init__(self) -> None:
        self.c: dict[str, int] = defaultdict(int)

    def add(self, k: str) -> None:
        self.c[k] += 1

    def remove(self, k: str) -> None:
        self.c[k] -= 1
        if self.c[k] <= 0:
            del self.c[k]

    def snapshot(self) -> dict[str, int]:
        return dict(self.c)


m = FreqManager()
m.add('a')
m.add('a')
m.remove('a')
print(m.snapshot())

Common mistakes

• Heap size bloated with stale entries—mark tombstones or store generation counters.
• Integer overflow in frequency sums in other languages (rare in Python int).

Key takeaways

• For “least frequent stack” problems, pair dict with stacks of stacks structure.
• Unit-test decrement paths as thoroughly as increments.