Coding Interview Patterns Module 3 – Arrays and hashing
Grouping with canonical keys
Group anagrams and other equivalent items in one pass with canonical keys: sorted-letter and count keys compared, and keys each language can hash.
What you will learn
- Design a canonical key that equivalent items share and no other items have
- Group items in one pass with a map from each key to its list of items
- Compare sorted-letter keys and count keys by their measured cost
- Choose keys that Python, JavaScript, Java, C++ and Go compare by value
- Apply canonical keys to shifted words, rotations and shapes on a grid
Before you start
What you’ll learn · Before you start
What you will learn
- Design a canonical key that equivalent items share and no other items have
- Group items in one pass with a map from each key to its list of items
- Compare sorted-letter keys and count keys by their measured cost
- Choose keys that Python, JavaScript, Java, C++ and Go compare by value
- Apply canonical keys to shifted words, rotations and shapes on a grid
Before you start
On this page
Grouping with canonical keys puts equivalent items together in one pass over a list. Every item gets a canonical key: A value computed from an item that every item equivalent to it shares and no other item has, such as a word's letters in sorted order for words made of the same letters. that all items equivalent to it share and no other item has, and a hash map files each item under its key, so each group forms as its items arrive: 100,000 words take 100,000 lookups instead of up to 5 × 10⁹ comparisons. For words made of the same letters, known as anagrams, the letters in alphabetical order make such a key: “rate”, “tear” and “tare” all become “aert”. The same idea groups any items once you can say what makes two of them “the same”. The problem known as group anagrams comes next in an original form, a word game with limits, together with the reason why comparing words with each other cannot meet them.
The problem: words made of the same letters
The problem
A word game collects the words its players type in a round. Group the words made of the same letters, each as many times, and return the groups: each group lists its words in the order they were typed, and the groups come in the order of their first words. A word typed twice joins its group twice. Limits: up to 100,000 words, each of 1 to 20 lowercase letters a to z.
["inch", "rate", "chin", "tear", "chain", "tare", "china"]gives[["inch", "chin"], ["rate", "tear", "tare"], ["chain", "china"]].["aa", "a", "aa"]gives[["aa", "aa"], ["a"]]: a repeat stays, and “a” has fewer letters than “aa”.["solo"]gives[["solo"]].
Equivalent words share a key
Text description of the diagram
Each word of the first example gets a key: its letters in alphabetical order. The words with the same key form one group, one row per key:
- key chin: inch and chin;
- key aert: rate, tear and tare;
- key achin: chain and china.
Words with the same key are made of the same letters, so each key stands for one group.
The brute force: compare with every group
Compare each word with the first word of every group formed so far, using the letter-count check of the previous lesson, and add it to the first group that matches, or start a new group. The worst case is a round in which no two words match, so every word is compared with every group:
"""Groups of words made of the same letters, by brute force: compare each word with every group so far."""
from collections import Counter
from itertools import combinations_with_replacement
def same_letters(a, b):
return len(a) == len(b) and Counter(a) == Counter(b)
def group_brute(words):
"""Returns (groups, comparisons): each word joins the first group whose first word has the same letters."""
groups = []
comparisons = 0
for word in words:
for group in groups:
comparisons += 1
if same_letters(group[0], word):
group.append(word)
break
else:
groups.append([word])
return groups, comparisons
print(group_brute(["inch", "rate", "chin", "tear", "chain", "tare", "china"])[0])
print(group_brute(["aa", "a", "aa"])[0])
print(group_brute(["solo"])[0])
# The slowest case: every word is its own group, so each word is compared with every group before it.
classes = ["".join(c) for c in combinations_with_replacement("abcdefghijklmnopqrstuvwxyz", 3)]
for n in (500, 1_000):
groups, comparisons = group_brute(classes[:n])
print(f"n = {n:,}: {len(groups):,} groups, {comparisons:,} comparisons")
n = 100_000
print(f"n = {n:,}: up to {n * (n - 1) // 2:,} comparisons")Output
[['inch', 'chin'], ['rate', 'tear', 'tare'], ['chain', 'china']] [['aa', 'aa'], ['a']] [['solo']] n = 500: 500 groups, 124,750 comparisons n = 1,000: 1,000 groups, 499,500 comparisons n = 100,000: up to 4,999,950,000 comparisons
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 groups_brute.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Doubling the words quadruples the comparisons: n(n − 1)/2 of them, each costing up to the length of a word. At 100,000 words that is about 5 × 10⁹ comparisons. Step through the first example to see each word compared with the groups:
The drawing shows the whole scene; its 8 steps are listed below.
Every step as text
- inch. The round is inch, rate, chin, tear, chain, tare and china. There is no group yet, so inch starts group 1 without a comparison.
- rate. rate is compared with inch, the first word of group 1. The letters differ, so rate starts group 2. 1 comparison so far.
- chin. chin is compared with inch and has the same letters, so it joins group 1 at the first comparison. 2 so far.
- tear. tear differs from inch and matches rate, so it joins group 2 after 2 comparisons. 4 so far.
- chain. chain matches neither inch nor rate, so it starts group 3 after 2 comparisons. 6 so far.
- tare. tare differs from inch and matches rate, so it joins group 2. 8 comparisons so far.
- china. china is compared with inch, rate and chain, and joins group 3 at the third comparison. 11 comparisons in all.
- The slowest round. Every new group adds one comparison for every later word. When no two words match, each word is compared with every group before it, n(n − 1)/2 comparisons in all.
What to notice
Two words belong together when something that ignores the order of letters is equal for both. If every word carries that something as a key, finding its group is one lookup in a hash map instead of a comparison with every group. Two keys are in common use for anagrams:
- A sorted-letters key writes a word’s letters in alphabetical order, so “tear” becomes “aert”. Building it sorts the word, which is quick for short words.
- A count key lists how many times each of the 26 letters appears in the word. It reads the word once, whatever its length, and then holds 26 numbers.
Checkpoint
Check: Groups of words made of the same letters · Comparing each word with every group · Sorted letters and letter counts as keys
Questions on the word game, its brute force and the two keys follow, beginning with the idea your answers show is weakest.
Practice that adapts to you
Practise this lesson
8 questions about 8 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Grouping in one pass, with the key’s contract Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- A key that is too coarse, and one Python refuses
- Keys that every language compares by value, in 14 languages
- Sorted keys against count keys, measured
- Other equivalences, other keys
- Variants, edge cases and the common bugs
- Edge cases and common bugs
- Variants
- Practice: group the rotations of each word
- Group the words that are rotations of each other
- Interview questions
- Group 10⁶ words of up to 30 lowercase letters into anagram classes within 2 seconds. Which canonical key do you build, what does each choice cost in time and memory, and would your answer change between Python and C++?
- A 1,000 × 1,000 grid holds islands of land cells. Count the distinct island shapes, where two islands have the same shape if one can be moved, turned or mirrored onto the other. What key do you give each island, and what does it cost?
- Sign-ups arrive as email addresses typed by users. The product team wants a warning when someone signs up again with "the same" address. Design the canonical key, and say which normalisations are safe and which can merge two different people.
- Key takeaways
1 diagram · 6 runnable examples (Java, JavaScript, Python) · 1 exercise with sample tests · 3 interview answers · about 30 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- canonical key
- A value computed from an item that every item equivalent to it shares and no other item has, such as a word's letters in sorted order for words made of the same letters.
- hashable
- Usable as a key of a hash map or a member of a set: the value's hash never changes while it is stored, and two equal values have equal hashes.
References
- Glossary: hashable (Python Software Foundation)
- Built-in types: mapping types (dict), dict.setdefault() (Python Software Foundation)
- Built-in types: str.count() (Python Software Foundation)
- ECMAScript language specification: Map objects (Ecma International (TC39))
- Java SE 25 API: Object.equals() and hashCode() (Oracle)
- Java SE 25 API: Record (the equals() of record components) (Oracle)
- Java SE 25 API: Arrays.toString(int[]) (Oracle)
- JEP 395: Records (OpenJDK)
- std::unordered_map (cppreference.com)
- std::hash (cppreference.com)
- The Go Programming Language Specification: map types and comparison operators (The Go Authors)
- Rust standard library: the array type (Eq and Hash) (The Rust Project)
- Kotlin: arrays (comparing arrays) (JetBrains)
- Dart API: List operator == (Dart (Google))
- Object.Equals Method (.NET API) (Microsoft)
- Ruby documentation: Array#hash and Array#eql? (Ruby)
- PHP manual: arrays (key types) (The PHP Group)
- Swift standard library: Array (Hashable conformance) (Apple)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress