Frequency Counting and Grouping
Use Counter and defaultdict to count character frequencies, group anagrams by sorted key, and find top-k frequent elements.
Frequency Counting and Grouping is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Frequency Counting: The Core Pattern
Frequency counting is among the most versatile patterns in coding interviews. By tallying how often each element appears in a list or string, you can answer questions about duplicates, anagrams, most-common elements, and valid arrangements in O(n) time — much better than the O(n log n) sort-and-scan alternative.
Python's Counter and defaultdict(int) are the standard tools. Both create a mapping from element to count; Counter additionally supports arithmetic and most_common.
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple']) # 3
print(freq['grape']) # 0 (not KeyError)
print(freq.most_common(2)) # [('apple',3),('banana',2)]Valid Anagram (LeetCode 242)
LeetCode 242 'Valid Anagram': determine if two strings are anagrams of each other. Two strings are anagrams if they have the same character frequencies. Compare their Counter objects or sort both strings. Using Counter is O(n), sorting is O(n log n). The Counter approach is optimal and directly expresses the definition.
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
if len(s) != len(t):
return False
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
for c in t: freq[ord(c) - ord('a')] -= 1
return all(f == 0 for f in freq)
print(isAnagram('anagram', 'nagaram')) # True
print(isAnagram('rat', 'car')) # False
print(isAnagram_arr('listen', 'silent')) # TrueGroup Anagrams (LeetCode 49)
LeetCode 49 'Group Anagrams': given a list of strings, group all anagrams together. Key insight: anagrams have the same sorted character sequence. Use a defaultdict(list) keyed by the sorted tuple of the string (tuples are hashable). Each group accumulates under the same key. Time: O(n × L log L) where L is the maximum string length.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # hashable canonical form
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(ord(c) - ord('a') for c in sorted(s))
groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
return list(groups.values())
Top K Frequent Elements (LeetCode 347)
LeetCode 347 'Top K Frequent Elements': return the k most frequent elements. A direct approach is O(n log n): count frequencies, sort by count descending, take first k. The optimal O(n) approach uses bucket sort: create buckets indexed by frequency (1 to n), place each element in its frequency bucket, then scan buckets from highest to lowest frequency collecting k elements.
from collections import Counter
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 result
print(topKFrequent([1,1,1,2,2,3], 2)) # [1, 2]
print(topKFrequent([1], 1)) # [1]Sort Characters by Frequency (LeetCode 451)
LeetCode 451 'Sort Characters By Frequency': rearrange a string so characters appear in descending order of frequency. Count frequencies, sort characters by frequency descending, and concatenate. Using most_common is the cleanest Python approach. Time: O(n log n) for sorting the unique characters by frequency.
from collections import Counter
def frequencySort(s):
freq = Counter(s)
return ''.join(ch * count for ch, count in freq.most_common())
print(frequencySort('tree')) # 'eetr' or 'eert'
print(frequencySort('cccaaa')) # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb')) # 'bbAa' or 'bbaA'Task Scheduler (LeetCode 621)
LeetCode 621 'Task Scheduler': given tasks and a cooldown n, find minimum time to finish all tasks. The critical insight: the most frequent task determines the structure. Arrange max_count copies of the most frequent task with (n) gaps. Total minimum time = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). If there are enough different tasks to fill the gaps, idle time is 0.
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_count = max(freq.values())
# How many tasks share the max frequency
num_max = sum(1 for v in freq.values() if v == max_count)
# Minimum slots needed based on most frequent task
min_slots = (max_count - 1) * (n + 1) + num_max
return max(min_slots, len(tasks))
print(leastInterval(['A','A','A','B','B','B'], 2)) # 8
print(leastInterval(['A','A','A','B','B','B'], 0)) # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2)) # 10Majority Voting with Counter
LeetCode 169 'Majority Element': find the element appearing more than n/2 times. While Boyer-Moore voting is the optimal O(1) space solution, using Counter.most_common(1) solves it directly in O(n) time and O(n) space. For interviews mentioning O(1) space, present Boyer-Moore as the follow-up; for interviews allowing extra space, Counter is cleaner.
from collections import Counter
def majorityElement_counter(nums):
freq = Counter(nums)
return freq.most_common(1)[0][0]
# Boyer-Moore O(1) space
def majorityElement_moore(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums)) # 2
print(majorityElement_moore(nums)) # 2First Non-Repeating Character
LeetCode 387 'First Unique Character in a String': find the index of the first character that appears exactly once. Two-pass approach: first pass builds a frequency count; second pass finds the first character with count 1. Time: O(n), Space: O(1) since the alphabet is fixed at 26 characters.
from collections import Counter
def firstUniqChar(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1
print(firstUniqChar('leetcode')) # 0 (l)
print(firstUniqChar('loveleetcode')) # 2 (v)
print(firstUniqChar('aabb')) # -1Subarray Sum Equals K (LeetCode 560)
LeetCode 560 'Subarray Sum Equals K': count subarrays summing to k. Brute force is O(n²). The O(n) approach: maintain a running prefix sum and a frequency map of prefix sums seen so far. For each position i, the count of subarrays ending at i with sum k equals the count of earlier prefix sums equal to (current_prefix_sum - k). Initialise the map with {0: 1} to handle subarrays starting from index 0.
from collections import defaultdict
def subarraySum(nums, k):
freq = defaultdict(int)
freq[0] = 1 # prefix sum of 0 seen once (empty prefix)
prefix_sum = 0
count = 0
for num in nums:
prefix_sum += num
# How many earlier prefix sums allow a k-sum subarray ending here
count += freq[prefix_sum - k]
freq[prefix_sum] += 1
return count
print(subarraySum([1, 1, 1], 2)) # 2
print(subarraySum([1, 2, 3], 3)) # 2
print(subarraySum([1, -1, 1, -1, 1], 0)) # 4Counter Arithmetic and Intersection
Counter supports arithmetic: + merges (adds counts), - subtracts (clips at 0), & takes the minimum (intersection), and | takes the maximum (union). These operations simplify problems like 'find common characters in multiple strings' or 'minimum character removals to make one string an anagram of another'.
from collections import Counter
A = Counter('abccdd')
B = Counter('ccdde')
print('Add: ', dict(A + B)) # sum of counts
print('Subtract: ', dict(A - B)) # A - B, clipped at 0
print('Intersect:', dict(A & B)) # min of shared counts
print('Union: ', dict(A | B)) # max counts
# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values())) # 5Summary: When to Use Frequency Counting
Reach for frequency counting when the problem involves: checking if two strings are equivalent up to reordering (anagram), finding the most/least common elements, validating that a collection has the right 'ingredients', or turning a subarray/substring problem into a prefix-sum-with-map problem. The key is that order within a group does not matter — only counts do.
Always use Counter for clarity; switch to a plain dict or array only when you need finer control or strict O(1) space with a bounded alphabet.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Counter provides O(n) frequency counting with most_common, arithmetic operators, and zero-default access, grouping by canonical form (sorted tuple) solves group-anagrams in O(nL log L), and prefix-sum with frequency map converts subarray-sum-k from O(n²) to O(n). Next up we tackle the longest consecutive sequence problem and LRU cache design.
Frequently asked questions
Is the “Frequency Counting and Grouping” lesson free?
Yes — the full text of “Frequency Counting and Grouping” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Frequency Counting and Grouping”?
Use Counter and defaultdict to count character frequencies, group anagrams by sorted key, and find top-k frequent elements. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Frequency Counting and Grouping” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Hash Function Internals and Collision Handling
- Two-Sum and Its Many Variants
- Frequency Counting and Grouping
- Longest Consecutive Sequence and LRU Cache