Counting & frequency maps
In one line
Count how often each value appears in one O(n) pass, then answer anagram, duplicate, majority and top-k questions from the counts.
What it is
A frequency map records value -> number of occurrences. In Python it is a dict or collections.Counter; when values come from a small fixed range (lowercase letters, digits), a plain array of 26 or 10 counters is even simpler and faster.
Once you have counts, many questions become easy: two strings are anagrams if their counts match, the first unique character is the first one with count 1, and the most frequent items are the ones with the largest counts.
Why interviewers ask
Counting is the first move for a large share of string and array questions, and interviewers expect you to see it quickly. They also probe the follow-ups: how to get the top k without sorting everything (heap or bucket sort), how to compare counts in a moving window, and when a fixed-size array beats a hash map.
How it works
- 1Pass over the input once, doing counts[x] += 1 for each element. O(n) time.
- 2Space is O(u), where u is the number of distinct values; for a fixed alphabet like 26 letters that is O(1).
- 3To compare two collections (anagrams), build both count maps and check they are equal, or add for one and subtract for the other and check that everything ends at zero.
- 4To find the k most frequent: sort the (value, count) pairs by count in O(u log u), use a heap of size k in O(u log k), or use bucket sort by count in O(n).
- 5Bucket sort works because a count can never exceed n: create buckets 0..n, put each value in buckets[count], then read buckets from high to low until you have k values.
Worked example · Top 2 frequent: nums = [1, 1, 1, 2, 2, 3], k = 2
- Count: freq = {1: 3, 2: 2, 3: 1}.
- Create buckets 0..6 (n = 6). Put each value at the index of its count: buckets[3] = [1], buckets[2] = [2], buckets[1] = [3].
- Scan from 6 down to 1. Buckets 6, 5 and 4 are empty.
- Bucket 3 gives value 1. result = [1].
- Bucket 2 gives value 2. result = [1, 2]. We have k = 2 values, stop.
- Total work: one counting pass plus one pass over n + 1 buckets, so O(n), with no sorting.
Picture it
It is like a teacher tallying a class vote on the board: one tick mark per vote as the papers are read once. After that, 'which option won?' and 'did any two options tie?' are answered by looking at the tallies, not by re-reading every paper.
Reference code
from collections import Counter
def top_k_frequent(nums, k):
freq = Counter(nums) # value -> count, O(n)
buckets = [[] for _ in range(len(nums) + 1)]
for val, c in freq.items(): # bucket index = count
buckets[c].append(val)
result = []
for c in range(len(buckets) - 1, 0, -1): # highest counts first
for val in buckets[c]:
result.append(val)
if len(result) == k:
return result
return result
def is_anagram(s, t):
return len(s) == len(t) and Counter(s) == Counter(t)
top_k_frequent counts with Counter, then places each value in a bucket indexed by its count. Since no count exceeds n, there are n + 1 buckets, and reading them from high to low yields the most frequent values in O(n) total. is_anagram compares the two count maps after a quick length check.
Key patterns
Anagram and permutation check
When: Do two strings use the same letters the same number of times?
How: Compare Counter(s) == Counter(t), or use one 26-slot array: +1 for s, -1 for t, all zeros means anagram.
Group by count signature
When: Group anagrams together
How: Key each word by a tuple of 26 letter counts (or its sorted letters) and append to map[key].
Top k frequent
When: Most common elements, words or errors
How: Count, then a heap of size k (O(u log k)) or bucket sort by count (O(n)).
First unique / first repeat
When: Find the first character that appears once, or the first that repeats
How: Count in one pass, then scan the input again in order and return the first with the needed count.
Counts in a moving window
When: Does any substring of s2 contain a permutation of s1?
How: Keep a count map for the current window; add the entering character and subtract the leaving one instead of recounting.
Real-world use
Word count in MapReduce and Spark
Word count is the classic first Hadoop and Spark job: mappers emit (word, 1), and the framework groups by word and sums, which is a frequency map spread over many machines.
Search and log analytics
Elasticsearch 'terms' aggregations return the most common values of a field, such as the top error codes in the last hour, by counting per shard and combining the counts.
Trending and heavy hitters at scale
When exact counts would use too much memory, streaming systems use approximate counters such as the Count-Min Sketch (available in Redis Stack) to find the most frequent items, like popular hashtags or noisy IP addresses.
Compression
Huffman coding, used inside DEFLATE (zip, gzip, PNG), starts by counting how often each symbol appears, then gives frequent symbols shorter codes.
In a project
A support team wants a dashboard showing the top 10 complaint keywords from 200,000 tickets per day, refreshed every 15 minutes.
- Tokenise each new ticket, drop stop words, and update a Counter of keyword -> count for the current day.
- Keep per-15-minute counters and add them up for the day, so new tickets only touch the latest small counter.
- Get the top 10 with heapq.nlargest(10, counts.items(), key=...) in O(u log 10) instead of sorting every distinct word.
- Store each day's counts so the dashboard can show week-over-week changes for each keyword.
Impact: The dashboard refreshes in well under a second instead of re-scanning every ticket, and the team spots emerging issues (a spike in 'refund' or 'login') within 15 minutes rather than at the weekly review.
Trade-offs
Use it when
- The question involves 'how many times', duplicates, anagrams, majority or most common
- You need to compare two collections ignoring order
- Values repeat a lot, so the map is much smaller than the input
Avoid it when
- Values come from a tiny fixed range: use an array of counters instead of a hash map
- The data stream is too large to count exactly in memory: use an approximate sketch
- You need O(1) extra space for a majority element: Boyer-Moore voting finds it without a map
Cost: Counting O(n) time, O(u) space (O(1) for a fixed alphabet). Top k: O(u log u) by sorting, O(u log k) with a heap, O(n) with bucket sort.
Common mistakes
- Sorting the whole array to count, which costs O(n log n) when one counting pass is O(n).
- Forgetting that strings of different lengths cannot be anagrams, or ignoring case and spaces when the question says to.
- Building a new Counter for every window position (O(n * k)) instead of updating one map as the window slides.
- Calling Counter.most_common() without arguments for top k, which sorts every distinct item; pass k or use a heap.
- Saying the counting map is O(1) space for arbitrary values; it is O(u). Only a fixed alphabet makes it constant.
Interview questions
Quick revision
- Counter(nums) or counts[x] += 1: one pass, O(n).
- Space O(u) distinct values; fixed alphabet = O(1).
- Anagram: equal counts (check lengths first).
- Group anagrams: key = sorted word or tuple of 26 counts.
- Top k: heap O(n log k) or bucket sort O(n).
- Bucket index = count; counts never exceed n.
- Sliding window: update counts, never rebuild.
- Majority element in O(1) space: Boyer-Moore voting.
Check yourself
1. What is the time complexity of building a frequency map of n elements with a hash map?
2. Why can bucket sort find the top k frequent elements in O(n)?
3. Which is the best key for grouping anagrams in O(L) time per word of length L?
4. s = 'listen', t = 'silent'. After +1 for each letter in s and -1 for each in t, what does a 26-slot array contain?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.