Frequency Counting
Frequency counting is exactly what it sounds like - count how many times each element appears. Simple idea, but it unlocks solutions to anagrams, duplicates, majority elements, and tons more.
The Core Idea
Use a hash map to count occurrences. One pass to count, then use those counts to solve the problem. It's O(n) time and O(k) space where k is the number of unique elements.
The Key Insight
Two things are anagrams if they have the same frequency counts. Two arrays match if their frequency maps match. Many "comparison" problems reduce to comparing counts.
Building a Frequency Map
from collections import Counter
# Using Counter (Pythonic way)
freq = Counter(items)
# Manual way
freq = {}
for item in items:
freq[item] = freq.get(item, 0) + 1Classic: Valid Anagram
def isAnagram(s, t):
return Counter(s) == Counter(t)Classic: Top K Frequent Elements
def topKFrequent(nums, k):
freq = Counter(nums)
# Bucket sort by frequency
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return resultClassic: First Unique Character
def firstUniqChar(s):
freq = Counter(s)
for i, char in enumerate(s):
if freq[char] == 1:
return i
return -1When to Use Frequency Counting
- Anagram problems - Compare character counts
- Finding duplicates - Count > 1
- Finding unique - Count == 1
- Majority element - Count > n/2
- Top K problems - Sort by frequency
- Sliding window - Maintain window frequencies
Pro Tip
For strings with only lowercase letters, you can use an array of size 26 instead of a hash map. Index = ord(char) - ord('a'). Faster and cleaner for known alphabets.