Run it
Both keys, plus the pairwise version with its comparisons counted, so the difference between six lookups and fifteen comparisons is a number on the screen rather than a claim.
Sorted characters:
O(n × m log m) for n words of length m. Simple, and it is the answer most people give.
Character counts:
O(n × m) — no sorting. The key is a 26-element tuple rather than a string, which is a fixed-size key regardless of word length.
| | Sorted key | Count key |
|---|
| Time | O(n m log m) | O(n m) |
| Key size | m | 26 (fixed) |
| Alphabet assumption | None | Lowercase ASCII |
| Readability | Better | Worse |
Which is better depends on m. For short words the sort is negligible and the sorted key is clearer; for long words or a large corpus the count key wins. For non-ASCII input the count array must become a dictionary or a Counter, at which point the sorted key is simpler again.
Why a tuple, not a list
groups[counts] with counts as a list raises TypeError: unhashable type: 'list'.
Dictionary keys must be hashable, which requires immutability — if a key could change after insertion, its hash would change and the entry would become unreachable. A tuple is immutable and hashable; a list is not.
That is a small detail and it is one interviewers specifically watch for, because it demonstrates understanding of why the restriction exists rather than merely remembering it.
The same applies to using a Counter as a key: Counter is a dict subclass and therefore unhashable. tuple(sorted(counter.items())) is the usual conversion.
The instinct, and why it is wrong
The obvious approach compares every word with every other word to see whether they are anagrams. That is n(n−1)/2 comparisons, each costing O(m log m) or O(m), so the whole thing is O(n²·m).
The realisation that fixes it: being anagrams is an equivalence relation, so instead of testing pairs you can give every word a label that all its anagrams share, and group by label. Dictionaries group by label in O(1) each.
Choosing the key
Sorted letters. "".join(sorted(word)). Simple, obviously correct, O(m log m) per word. This is the answer to give.
A count tuple. A 26-element tuple of letter counts, built in O(m). Faster for long words, and the improvement to mention when asked. It must be a tuple, not a list — keys have to be hashable.
Total cost is O(n·m log m) with sorting, or O(n·m) with counts. Either way the n² is gone.
The pattern behind it
"Canonicalise, then group" solves a whole family of questions: find duplicate files by hashing contents, group points by slope, detect isomorphic strings by normalising the pattern. Whenever a question asks you to find things that are equivalent under some transformation, look for the canonical form before you look for a clever comparison.
Walking through the example
["eat", "tea", "tan", "ate", "nat", "bat"] with the sorted key:
| Word | Key | Groups after |
|---|
| eat | aet | {aet: [eat]} |
| tea | aet | {aet: [eat, tea]} |
| tan | ant | {aet: [...], ant: [tan]} |
| ate | aet | {aet: [eat, tea, ate], ...} |
| nat | ant | {..., ant: [tan, nat]} |
| bat | abt | {..., abt: [bat]} |
One pass, and the grouping falls out of the dictionary. Note that the output order depends on insertion order, which Python dictionaries preserve — so the groups come out in the order their first member appeared. If the expected output has a specific order, that must be stated.
Edge cases
| Case | Handling |
|---|
| Empty input | Returns [] |
| Single word | One group of one |
| All words identical | One group — a word is an anagram of itself |
| Words of different lengths | Different keys automatically |
| Empty strings in the input | Group together under the empty key |
| Duplicate words | Both appear in the same group |
| Mixed case | Different keys unless normalised — ask |
| Non-ASCII | Count array breaks; use sorted or a Counter |
The mixed-case row is worth raising: "Eat" and "tea" are anagrams under a case-insensitive reading and not under a strict one. Ask.
The follow-ups
"What if the words are very long?" The count key avoids the sort, giving O(m) per word instead of O(m log m).
"What about a huge corpus that does not fit in memory?" Compute the key per word and partition by hash across machines or files — all anagrams share a key, so they land in the same partition. This is a MapReduce shape: the key is the map output, and the grouping is the shuffle.
"Find all anagrams of one word in a list." Compute that word's key once and filter, O(n m). No dictionary needed.
"Find all anagram substrings of a pattern in a longer string." A sliding window of the pattern's length with an incrementally updated count — O(n) rather than re-counting each window.
"What if we want groups sorted by size?" Sort the result by len, which is a one-line addition and a reasonable clarification to offer.
What it is testing
Do you find a canonical form instead of comparing pairs? That is the whole idea, and it is the transferable one.
Do you know dictionary keys must be hashable, and why?
Do you use defaultdict rather than checking whether each key exists?
Do you state the complexity in terms of both n and m? Saying "O(n log n)" here is imprecise — the sort is per word, over its length.
Do you notice the count-key optimisation when prompted about long words?
The canonical-form idea appears far beyond this problem: deduplication by content hash, caching by a normalised request, database indexing by a computed column. Any time "these two things are equivalent" needs to be fast, computing a canonical key and using a dictionary is the answer.
Recap in one screen
- Compute a canonical form per word and group with a dictionary — one pass, no pairwise comparison.
- Sorted characters is the clear key at O(m log m); a 26-element count tuple is O(m) and fixed size.
- Keys must be hashable, so use a tuple rather than a list or a
Counter. defaultdict(list) removes the key-existence check.- The canonical-key pattern generalises to deduplication, caching and indexing.