Frequency Counter —
Count once. Compare in O(1).
The frequency counter pattern replaces O(n²) nested loops with two O(n) passes using a hash map. Instead of comparing every element against every other element, you count occurrences of each value once — then compare counts. Watch the frequency map build on LearnBug and the pattern becomes instinctive for any counting problem.
What is the Frequency Counter pattern?
A frequency counter uses a hash map (or Python's Counter) to tally how many times each element appears. Once built, you can compare two frequency maps in O(k) time where k is the number of unique elements. Classic uses: anagram detection, checking if one array is a permutation of another, and finding the most common element.
Why it beats nested loops
Without a frequency map, checking if two arrays have the same elements requires comparing every element of one against every element of the other — O(n²). With frequency maps, build each in O(n) and compare in O(k) — total O(n). On LearnBug you watch the map fill up as each element increments its count, then the two maps compare side by side.
Are [1, 2, 3, 2, 1] and [3, 1, 2, 1, 2] the same multiset?
Build a frequency map for each, then compare.
Build frequency map for Array A: [1, 2, 3, 2, 1]
Scan left to right. Each element increments its count in the map. Default count is 0.
Build frequency map for Array B: [3, 1, 2, 1, 2]
Same process on B. Order doesn't matter — we only care about counts.
Compare the two maps
For each key in Map A, check if Map B has the same count. 1:2 ✓, 2:2 ✓, 3:1 ✓. All match — same multiset.
Map A
Map B
All counts match → True ✓
Three frequency counter implementations
Time & Space Complexity
Frequently asked questions
When should I reach for the frequency counter pattern?
Any time you need to: count how many times something occurs, check if two collections have the same elements (with multiplicity), find the most/least frequent element, detect duplicates, or check if one sequence is a permutation of another. If the problem involves counting or comparing counts — frequency map.
What is Python's Counter and how does it differ from a plain dict?
Counter is a dict subclass from collections that defaults missing keys to 0 (no KeyError), supports arithmetic between counters (add, subtract, intersection, union), and has most_common(n) for the top n elements. It's the Pythonic way to build frequency maps.
How does the one-pass approach work?
Use a single map: increment the count for each element in array1, decrement for each element in array2. If all counts end at 0, the arrays have identical frequencies. This uses O(k) space with one map instead of two, and processes both arrays in a single zip pass.
What are common interview problems using frequency counter?
Valid Anagram (LC 242), Find All Anagrams in a String (LC 438), Top K Frequent Elements (LC 347), First Unique Character in a String (LC 387), Minimum Window Substring (LC 76 — sliding window + frequency map), and Ransom Note (LC 383). Frequency counter is one of the most broadly applicable hash map patterns.
Can I use a list instead of a dict for character frequency?
Yes — for lowercase English letters, a list of size 26 (indexed by ord(c) - ord('a')) works and is O(1) lookup with lower constant factors than a hash map. The trade-off: only works when the key range is small and known in advance. For arbitrary integers or strings, a dict is more general.
Watch the frequency map fill up on your own input
Paste your array into LearnBug and see every element increment its count in the map step by step.