VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 02: Hashing

Lesson 2.5 of 12 in this moduleFree

Group Anagrams

Group words that are anagrams of each other: from comparing every pair, to a canonical key per word in one pass, and how to choose that key (sorted letters versus a 26-count tuple) from the word lengths. Then Unicode, huge inputs and grouping embeddings by a hashed signature.

about 10 min 5 Python examples 2 quick checks

Problem. Given a list of words, group the anagrams together (in any order).

text
["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.

python
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.

each word maps to its sorted-letters key: eat, tea and ate to aet; tan and nat to ant; bat to abt; each key's bucket collects its words.
Diagram— each word maps to its sorted-letters key: eat, tea and ate to aet; tan and nat to ant; bat to abt; each key's bucket collects its words.

Key A: the sorted letters

python
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.

python
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

work per word for a sorted key (k log k) and a count key (k + 26): about 12 versus 31 for 5-letter words, 282 versus 76 for 50 characters, and about 4,485 versus 526 for 500 characters.
Chart— work per word for a sorted key (k log k) and a count key (k + 26): about 12 versus 31 for 5-letter words, 282 versus 76 for 50 characters, and about 4,485 versus 526 for 500 characters.
  • Short words (k ≲ 20): the sorted key is shorter to write, uses a compact string key, and sorted runs 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?

  1. Count tuples are always faster
  2. 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
  3. Sorting is wrong for long strings
  4. Tuples can't be dict keys
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.

python
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.

python
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?

  1. How to compute a cheap key such that items that belong together get the same key, so grouping becomes hashing
  2. Which sorting algorithm to use
  3. How many machines to use
  4. Whether to use recursion
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

  1. What's the repeated work in the pairwise brute force?
  2. Why does a canonical key remove pairwise comparisons entirely?
  3. Compare the sorted key and the count key in cost and key size.
  4. Why might the sorted key be faster for short words in Python?
  5. How does this problem map onto MapReduce?
  6. How does LSH extend the idea to similar items?
Answers
  1. Each word's canonical form is recomputed in every comparison.
  2. Anagrams have the same key, so a dictionary sends each word directly to its group.
  3. Sorted: O(k log k) time, key of length k. Count: O(k + 26) time, fixed 26-entry key.
  4. sorted runs in C, while the count loop is interpreted Python with a fixed 26-slot overhead.
  5. Map each word to (key, word), shuffle so equal keys meet, then group: the same key design.
  6. It builds keys (e.g. signs of random projections) that similar vectors usually share, so similar items land in the same bucket.