Hash map frequency counting
Anagrams, duplicates, majority element, two-sum, and top-k frequent items.
High interview relevanceRoadmap: Beginner
| Time | Expected O(n) total |
|---|---|
| Space | O(n) |
Why it costs this much
One pass over the input, with an expected O(1) dictionary update for each item.
Code
from collections import Counter
counts = Counter(items) # one pass, expected O(1) per update
most_common = counts.most_common(1) # scans the k distinct keys: O(k)Common pitfalls
The bound is expected, not guaranteed, because it relies on hashing. Sorting items by frequency afterward costs O(n log n).