Problem. Given a list of words, group the anagrams together (in any order).
["eat", "tea", "tan", "ate", "nat", "bat"]
→ [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
ML context. "Group items that are equivalent under some rule" is bucketing by a key, the basis of GROUP BY
in SQL and groupby in pandas. The same pattern drives deduplication (group by a content hash), blocking in
entity resolution (only compare records sharing a key) and locality-sensitive hashing (group similar embeddings
by a hashed signature). Lesson 1.7 introduced the signature idea; here we make it the main tool and learn to choose
the key.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| m words, each of length up to k? | m ≤ 10⁴, k ≤ 100 | O(m²) pairwise ≈ 10⁸ checks |
| Characters? | Lowercase a–z | Allows a 26-slot count key |
| Output order? | Any | No sorting of groups needed |
| Duplicates in the input? | Possible | Each copy goes in its group |
2. Step 2: Brute force: compare every pair
For each word not yet grouped, scan the remaining words and pull in its anagrams.
def group_anagrams_brute(words):
used = [False] * len(words)
groups = []
for i, w in enumerate(words):
if used[i]:
continue
group = [w]
used[i] = True
for j in range(i + 1, len(words)):
if not used[j] and sorted(words[j]) == sorted(w): # anagram check: O(k log k)
group.append(words[j])
used[j] = True
groups.append(group)
return groups
result = group_anagrams_brute(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(sorted(g) for g in result) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
print("pairwise grouping works: O(m² · k log k) time")
O(m² · k log k): with 10⁴ words that's up to 5 × 10⁷ pair checks, each sorting two words. The repeated work: each word's sorted form is recomputed for every comparison.
3. Step 3: Optimise: compute a key once, then hash
First principles: anagrams share a canonical form (lesson 1.7). Compute it once per word and use it as a dictionary key; every word goes straight to its group's bucket. No pairwise comparisons at all.
Key A: the sorted letters
from collections import defaultdict
def group_anagrams_sorted(words):
groups = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w) # O(k log k) per word
return list(groups.values())
result = group_anagrams_sorted(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(sorted(g) for g in result) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
print("sorted-key grouping: O(m · k log k) time, O(m · k) space")
Key B: the letter counts
A 26-count tuple is also a canonical form, and computing it is O(k + 26): linear in the word length.
import random
from collections import defaultdict
def group_anagrams_count(words):
groups = defaultdict(list)
for w in words:
counts = [0] * 26
for ch in w:
counts[ord(ch) - 97] += 1
groups[tuple(counts)].append(w) # O(k + 26) per word
return list(groups.values())
def canon(groups):
return sorted(sorted(g) for g in groups)
def brute(words):
used, out = [False] * len(words), []
for i, w in enumerate(words):
if used[i]:
continue
g = [w]
used[i] = True
for j in range(i + 1, len(words)):
if not used[j] and sorted(words[j]) == sorted(w):
g.append(words[j])
used[j] = True
out.append(g)
return out
rng = random.Random(42)
for _ in range(500):
words = ["".join(rng.choice("abc") for _ in range(rng.randint(0, 4))) for _ in range(rng.randint(0, 10))]
assert canon(group_anagrams_count(words)) == canon(brute(words))
print("count-key grouping matches brute force: O(m · (k + 26)) time")
Choosing the key from the constraints
- Short words (k ≲ 20): the sorted key is shorter to write, uses a compact string key, and
sortedruns in C. It's usually as fast or faster in Python. - Long strings (k in the hundreds or more): the count key's O(k) beats O(k log k), and its key size is fixed at 26 entries no matter how long the string.
Big-O tells you which wins eventually; the constant factors and key sizes decide small cases. Measure if it matters.
Quick check
Why does a count-tuple key beat a sorted-letters key for very long strings but not necessarily for short words?
Show the answer
B. Counting is O(k + 26) versus O(k log k) for sorting, so it wins as k grows; for short words the +26 overhead and Python-level loop can make sorting (done in C) as fast or faster — Asymptotic advantage matters for large k; constants dominate for small k.
4. When the constraints change
| If the constraint becomes… | Best key / approach | Time | Space |
|---|---|---|---|
| Classic, short words | Sorted letters as key | O(m · k log k) | O(m · k) |
| Long strings, a–z | 26-count tuple | O(m · (k + 26)) | O(m · (k + 26)) |
| Unicode | frozenset(Counter(w).items()) or sorted string |
O(m · k log k) | O(m · k) |
| Only group sizes needed | Counter over keys |
same | O(groups) keys only |
| Doesn't fit in memory | Sort or shuffle by key (MapReduce), then group | O(N log N) external | streaming |
| Group similar, not identical, items | Locality-sensitive hashing (signature buckets) | ~O(m · d) | O(m) |
Change A: only the sizes of the groups
If you just need "how many anagram families, and how big", store counts per key instead of word lists.
from collections import Counter
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
sizes = Counter("".join(sorted(w)) for w in words)
assert sorted(sizes.values(), reverse=True) == [3, 2, 1]
print("family sizes:", dict(sizes))
Change B: too much data for one machine
Grouping by key is exactly what MapReduce and Spark do: each worker computes (key, word) pairs, the system
shuffles all pairs with the same key to the same worker, and each worker builds its groups. The key design
question is identical to ours: a cheap, canonical key.
Change C: group similar embeddings (locality-sensitive hashing)
For embeddings, "same group" means "close", not "identical". Random-hyperplane LSH builds a key from the signs of a few random projections: similar vectors usually get the same bit pattern. Grouping by that key is our dictionary again, now for approximate nearest-neighbour search.
import numpy as np
from collections import defaultdict
rng = np.random.default_rng(43)
planes = rng.normal(size=(8, 16)) # 8 random hyperplanes in 16 dims
def lsh_key(v):
return tuple((planes @ v > 0).astype(int)) # 8-bit signature
base = rng.normal(size=16)
near = base + 0.01 * rng.normal(size=16) # a tiny perturbation
far = -base # the opposite direction
assert lsh_key(base) == lsh_key(near) # same bucket (very likely; fixed seed)
assert lsh_key(base) != lsh_key(far) # every bit flips
buckets = defaultdict(list)
for name, v in [("base", base), ("near", near), ("far", far)]:
buckets[lsh_key(v)].append(name)
assert sorted(len(b) for b in buckets.values()) == [1, 2]
print("LSH groups similar vectors with the same dictionary pattern")
Quick check
What's the shared design question between grouping anagrams, a MapReduce GROUP BY and LSH?
Show the answer
A. How to compute a cheap key such that items that belong together get the same key, so grouping becomes hashing — In all three, choosing the key turns an all-pairs comparison into one pass of hashing.
5. Saying it out loud
"Comparing every pair of words is O(m² · k log k). Anagrams share a canonical form, so I compute a key once per word and group in a dictionary: one pass. The sorted letters cost O(k log k) per word; a 26-count tuple costs O(k + 26), which wins for long strings. If the data didn't fit in memory, it's a GROUP BY: shuffle by key. For similar rather than identical items, I'd use an LSH signature as the key."
Check yourself
- What's the repeated work in the pairwise brute force?
- Why does a canonical key remove pairwise comparisons entirely?
- Compare the sorted key and the count key in cost and key size.
- Why might the sorted key be faster for short words in Python?
- How does this problem map onto MapReduce?
- How does LSH extend the idea to similar items?
Answers
- Each word's canonical form is recomputed in every comparison.
- Anagrams have the same key, so a dictionary sends each word directly to its group.
- Sorted: O(k log k) time, key of length k. Count: O(k + 26) time, fixed 26-entry key.
sortedruns in C, while the count loop is interpreted Python with a fixed 26-slot overhead.- Map each word to (key, word), shuffle so equal keys meet, then group: the same key design.
- It builds keys (e.g. signs of random projections) that similar vectors usually share, so similar items land in the same bucket.