Hash Tables6 min read

Frequency Patterns

Count once, answer anything — the hash map superpower
count all: \(O(n)\)lookup count: \(O(1)\)space: \(O(k)\) where k=unique elements

The frequency pattern is one of the most common hash map tricks in coding interviews. The idea: spend \(O(n)\) time building a count map once, then answer any frequency-based query in \(O(1)\).

Think of it like a vote tally board at an election. Instead of re-counting ballots every time someone asks "how many votes did candidate X get?", you keep a running tally on the board. One pass through the ballots, then instant answers forever.

Anagram Detection

Two strings are anagrams if they have the same character frequencies. Sort both → \(O(n \log n)\) and awkward. Use frequency maps instead:

pseudocode
1
2
3
4
5
6
7
8
9
def is_anagram(s, t):
    if len(s) != len(t): return False
    count = {}
    for c in s: count[c] = count.get(c, 0) + 1
    for c in t:
        if c not in count or count[c] == 0:
            return False
        count[c] -= 1
    return True  # O(n) time, O(k) space

Duplicate Detection

"Has any element appeared more than once?" — add each element to a Set. First time you try to add something already in the Set, you've found a duplicate. \(O(n)\) time, \(O(n)\) space. Beats the \(O(n^2)\) nested loop approach.

◈ Watch frequency counting

← → arrow keys to step · click elements to interact

Frequency Count Pattern

from collections import Counter


# Anagram check using frequency maps
def is_anagram(s, t):
    return Counter(s) == Counter(t)


print(is_anagram('anagram', 'nagaram'))  # True
print(is_anagram('rat', 'car'))          # False


# Top-k most frequent
words = ['apple','banana','apple','cherry','banana','apple']
counter = Counter(words)
print(counter.most_common(2))  # [('apple', 3), ('banana', 2)]
Output
True
False
[('apple', 3), ('banana', 2)]

Top-K Frequent Elements

Given an array, find the k most frequent elements. Naive approach: sort by frequency → \(O(n \log n)\). Better approach:

  1. Build frequency map: \(O(n)\)
  2. Use a min-heap of size k: iterate frequency map, push each (freq, element) into the heap. If heap grows beyond k, pop the minimum. Total: \(O(n \log k)\)
  3. Or use bucket sort: create buckets indexed by frequency (max frequency = n), scatter elements into buckets, then read top-k from the back. \(O(n)\) time!

Sliding Window with Frequency

Problems like "longest substring with at most k distinct characters" combine the sliding window technique with a frequency map. The map tracks how many of each character are in the current window. When distinct count exceeds k, shrink from the left, decrementing frequencies and removing entries that drop to zero.

pseudocode
1
2
3
4
5
6
7
8
9
10
11
def longest_k_distinct(s, k):
    freq, left, best = {}, 0, 0
    for right, c in enumerate(s):
        freq[c] = freq.get(c, 0) + 1
        while len(freq) > k:
            l = s[left]
            freq[l] -= 1
            if freq[l] == 0: del freq[l]
            left += 1
        best = max(best, right - left + 1)
    return best
Note: Whenever a problem mentions 'count', 'frequency', 'most common', 'duplicate', or 'anagram' — draw a frequency map immediately. It almost always leads to the optimal solution.

Complexity

Build frequency mapOne pass through the input
Linear\(O(n)\)
Lookup any countDirect hash map lookup
Instant\(O(1)\)
Top-K with min-heapBetter than \(O(n \log n)\) sort when k is small
n log k\(O(n \log k)\)
Top-K with bucket sortFrequency as bucket index; frequencies bounded by n
Linear\(O(n)\)
Spacek = number of distinct elements; k ≤ n
Unique keys\(O(k)\)

Valid Anagram Groups

from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = tuple(sorted(w))
        groups[key].append(w)
    return list(groups.values())


result = group_anagrams(['eat','tea','tan','ate','nat','bat'])
for g in sorted(result, key=len, reverse=True):
    print(sorted(g))
Output
['ate', 'eat', 'tea']
['nat', 'tan']
['bat']
Challenge

Quick check

What is the time complexity of checking whether two strings are anagrams using frequency maps?

Continue reading

Sets & Maps
Instant membership and key-value lookup — the everyday hash table
→
Sliding Window
A picture frame scanning over an array to solve sub-array problems in \(O(n)\) time
→
Prefix Sums
Pre-calculate a running total so you can sum any subarray in instant \(O(1)\) time
→