Group Anagrams (LeetCode 49)
You get a list of words strs, all written in lowercase letters. Two words are anagrams of each other when you can reorder the letters of one to spell the other, so they use exactly the same letters, each the same number of times: "eat" and "tea" are anagrams, "aab" and "abb" are not.
Split strs into groups so that each group holds every word that is an anagram of the others in it, and return the list of groups. A word that has no anagram in the list forms a group on its own, and a word that appears twice is listed twice. The groups can come in any order, and so can the words inside each group.
Worked Examples
strs = ["eat","tea","tan","ate","nat","bat"][["bat"],["nat","tan"],["ate","eat","tea"]]"ate", "eat" and "tea" all sort to "aet"; "nat" and "tan" both sort to "ant"; nothing else sorts to "abt", so "bat" stands alone.strs = [""][[""]]strs = ["a"][["a"]]⚖️Formal Constraints & Bounds
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Core Insight
Anagrams become the same string once their letters are sorted, so the sorted word is a key they all share: one hash-map lookup per word files it with its anagrams, and no two words are ever compared.
Real-World Scenario & Production Applications
Deduplicating records works the same way: normalize each record to a canonical key (a lowercased email, a name's sorted tokens) and bucket by that key, so every record with the same key lands with its twins in one pass. Search engines group spelling variants and log pipelines count events by type with the same move: choose the key, hash it, and each item costs one lookup.
Step-by-Step Execution Trace Table
Input strs = ["eat","tea","tan","ate","nat","bat"] (LeetCode Example 1):
| Step | s | key = "".join(sorted(s)) | Key seen before? | groups after the step |
|---|---|---|---|---|
| 1 | "eat" | "aet" | No: start a group | {"aet": ["eat"]} |
| 2 | "tea" | "aet" | Yes: join it | {"aet": ["eat","tea"]} |
| 3 | "tan" | "ant" | No: start a group | {"aet": ["eat","tea"], "ant": ["tan"]} |
| 4 | "ate" | "aet" | Yes: join it | {"aet": ["eat","tea","ate"], "ant": ["tan"]} |
| 5 | "nat" | "ant" | Yes: join it | {"aet": [...], "ant": ["tan","nat"]} |
| 6 | "bat" | "abt" | No: start a group | {"aet": [...], "ant": [...], "abt": ["bat"]} |
| End | return [["eat","tea","ate"],["tan","nat"],["bat"]]: the same groups as LeetCode's output, in another order |
| 1 | Anagrams have the same letters with the same counts, so sorting a word gives one key that every anagram shares: `"tea"` and `"ate"` both become `"aet"`. |
| 2 | Keep a map `groups` from each key to every word read so far with that key; a word joins the list under `"".join(sorted(s))`, or starts it when the key is new. |
| 3 | `groups = defaultdict(list)`; `for s in strs:` compute `key`, then `groups[key].append(s)`; after the loop `return list(groups.values())`. |
| 4 | The trap: the key must keep repeated letters and be hashable. Use `"".join(sorted(s))`, never `frozenset(s)` or `set(s)` (they merge `"aab"` and `"abb"`) and never the bare list `sorted(s)` (unhashable). |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash map answers two questions in one step: "have I seen this key before?" and "what did I store with it?" So most hash-map solutions are one decision: what should the key be? For Group Anagrams, two words belong together exactly when they use the same letters the same number of times. Sorting a word's letters gives the same string for every anagram ("eat", "tea" and "ate" all become "aet"), so the sorted word is the key, and the value is the list of words that produced it.
🏟️ The Analogy: A Post Room With Labelled Pigeonholes
A clerk sorting mail doesn't compare each letter with every other letter. She reads the label that matters (the postcode), walks to that pigeonhole, and drops the letter in; a new postcode gets a new pigeonhole. At the end, each pigeonhole is one group. Here the "postcode" is the sorted word, and the pigeonholes are the entries of groups.
🔑 Why It Works
The key must be exact: equal for every pair of anagrams and different for everything else. "".join(sorted(s)) keeps repeated letters, so "aab" and "abb" get different keys. A frozenset(s) key would drop the repeats and merge them, and sorted(s) on its own is a list, which a dict can't use as a key.
A lossy key: key on
"".join(sorted(s)), never onfrozenset(s)orset(s). A set drops repeated letters, so"aab"and"abb"would land in one group.An unhashable key:
sorted(s)returns a list, and a list can't be a dict key (TypeError: unhashable type). Join it into a string or wrap it intuple(...).A plain dict without a default:
groups[key].append(s)raisesKeyErroron the first word of each key unlessgroupsis adefaultdict(list)(or you usegroups.setdefault(key, [])).Dropping the empty word:
""is a real word whose key is"";[""]must return[[""]], not[].Comparing words pairwise: checking each word against every group already built is O(N^2) comparisons; the map's lookup makes each word one step.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Group the anagrams together" and "in any order": the answer is a set of buckets, and anagrams are exactly the words that look the same once their letters are sorted. Items that belong together because they share a key you can compute from each one: the Hash Map model. Turn each word into its key and let the map collect the words.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision per word: s joins the list stored under "".join(sorted(s)), or starts that list when the key is new; no word is ever compared with another.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
return list(groups.values()): the answer is the groups; returninggroupsor its keys gives the dict or the sorted keys such as"aet".
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Hash Map, keyed by a canonical form of each word. Two words are anagrams exactly when their sorted letters match, so I sort each word and join the letters back into a string: that's the key. The map sends each key to the list of words that produced it, so a single pass files every word with its anagrams, and I never compare two words with each other. The trap is a lossy key: it must keep every letter with its count, so a set of letters won't do, and it must be hashable, which is why I join the sorted list into a string. At the end I return the map's values. With N words of up to K letters, sorting dominates: O(N times K log K) time and O(N times K) space. For long words, a 26-slot letter count as the key removes the log factor.
Complexity & Mathematical Proof
O(N * K log K)
Look at the code: for s in strs runs N times. Inside, sorted(s) sorts at most K letters in O(K log K), "".join(...) builds a K-letter string in O(K), and groups[key].append(s) hashes that K-letter key in O(K) and appends in O(1) on average. Each word costs O(K log K), so the loop costs O(N * K log K). list(groups.values()) at the end touches each group once, O(N).
O(N * K)
Every distinct key is a string of up to K letters and there are at most N of them, so the keys take O(N * K). The lists in groups only hold references to the input words, one per word: O(N), and they are also the output. Each sorted(s) builds a temporary list of K letters, O(K), freed before the next word.
T = N · (O(K log K) sort + O(K) join + O(K) hash) = O(N · K log K)
Derivation Progression
N iterations
for s in strs handles each word exactly once.
O(K log K) + O(K) per word
sorted(s) sorts the word's letters; "".join(...) turns the list into a string.
O(K) per word, on average
groups[key] hashes the K-letter key once; .append(s) adds the word in O(1).
O(N · K log K)
The sort dominates each iteration; returning list(groups.values()) adds only O(N).
Variable Definitions
Number of words in strs (1 to 10^4)
Length of the longest word (0 to 100)
"".join(sorted(s)): the word's letters in alphabetical order
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N · K): up to N distinct keys of up to K letters, plus one O(K) sorted list at a time
O(N) references to the input words, grouped (not counted)
Boundary Best / Worst Cases
: every word has at most one letter, so each sort and each key is constant work
: every word has K = 100 letters
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
At scale the same signal reads "group records by a property computed from each one": deduplicating near-identical items, or bucketing log lines by their normalized template. Designing the key is the whole problem there: it must be exact, cheap to compute and small to store.
words of letters. Pairwise comparison is , about steps at the limits; one sorted key per word is , about .
At scale, the keys themselves cost memory (), and a skewed key (one huge group) turns into one hot bucket; when the words arrive as a stream or don't fit in memory, group in two passes: partition by hash(key) % P to disk, then group each partition.
Core Algorithmic State Invariants
- Groups Come Out in First-Seen Order
A Python dict keeps insertion order, so list(groups.values()) lists the groups in the order their first word appeared, each with its words in input order. LeetCode accepts any order, so nothing needs sorting.
Group Anagrams (LeetCode 49)
You get a list of words strs, all written in lowercase letters. Two words are anagrams of each other when you can reorder the letters of one to spell the other, so they use exactly the same letters, each the same number of times: "eat" and "tea" are anagrams, "aab" and "abb" are not.
Split strs into groups so that each group holds every word that is an anagram of the others in it, and return the list of groups. A word that has no anagram in the list forms a group on its own, and a word that appears twice is listed twice. The groups can come in any order, and so can the words inside each group.
Worked Examples
strs = ["eat","tea","tan","ate","nat","bat"][["bat"],["nat","tan"],["ate","eat","tea"]]"ate", "eat" and "tea" all sort to "aet"; "nat" and "tan" both sort to "ant"; nothing else sorts to "abt", so "bat" stands alone.strs = [""][[""]]strs = ["a"][["a"]]⚖️Formal Constraints & Bounds
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Core Insight
Anagrams become the same string once their letters are sorted, so the sorted word is a key they all share: one hash-map lookup per word files it with its anagrams, and no two words are ever compared.
Real-World Scenario & Production Applications
Deduplicating records works the same way: normalize each record to a canonical key (a lowercased email, a name's sorted tokens) and bucket by that key, so every record with the same key lands with its twins in one pass. Search engines group spelling variants and log pipelines count events by type with the same move: choose the key, hash it, and each item costs one lookup.
Step-by-Step Execution Trace Table
Input strs = ["eat","tea","tan","ate","nat","bat"] (LeetCode Example 1):
| Step | s | key = "".join(sorted(s)) | Key seen before? | groups after the step |
|---|---|---|---|---|
| 1 | "eat" | "aet" | No: start a group | {"aet": ["eat"]} |
| 2 | "tea" | "aet" | Yes: join it | {"aet": ["eat","tea"]} |
| 3 | "tan" | "ant" | No: start a group | {"aet": ["eat","tea"], "ant": ["tan"]} |
| 4 | "ate" | "aet" | Yes: join it | {"aet": ["eat","tea","ate"], "ant": ["tan"]} |
| 5 | "nat" | "ant" | Yes: join it | {"aet": [...], "ant": ["tan","nat"]} |
| 6 | "bat" | "abt" | No: start a group | {"aet": [...], "ant": [...], "abt": ["bat"]} |
| End | return [["eat","tea","ate"],["tan","nat"],["bat"]]: the same groups as LeetCode's output, in another order |
| 1 | Anagrams have the same letters with the same counts, so sorting a word gives one key that every anagram shares: `"tea"` and `"ate"` both become `"aet"`. |
| 2 | Keep a map `groups` from each key to every word read so far with that key; a word joins the list under `"".join(sorted(s))`, or starts it when the key is new. |
| 3 | `groups = defaultdict(list)`; `for s in strs:` compute `key`, then `groups[key].append(s)`; after the loop `return list(groups.values())`. |
| 4 | The trap: the key must keep repeated letters and be hashable. Use `"".join(sorted(s))`, never `frozenset(s)` or `set(s)` (they merge `"aab"` and `"abb"`) and never the bare list `sorted(s)` (unhashable). |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash map answers two questions in one step: "have I seen this key before?" and "what did I store with it?" So most hash-map solutions are one decision: what should the key be? For Group Anagrams, two words belong together exactly when they use the same letters the same number of times. Sorting a word's letters gives the same string for every anagram ("eat", "tea" and "ate" all become "aet"), so the sorted word is the key, and the value is the list of words that produced it.
🏟️ The Analogy: A Post Room With Labelled Pigeonholes
A clerk sorting mail doesn't compare each letter with every other letter. She reads the label that matters (the postcode), walks to that pigeonhole, and drops the letter in; a new postcode gets a new pigeonhole. At the end, each pigeonhole is one group. Here the "postcode" is the sorted word, and the pigeonholes are the entries of groups.
🔑 Why It Works
The key must be exact: equal for every pair of anagrams and different for everything else. "".join(sorted(s)) keeps repeated letters, so "aab" and "abb" get different keys. A frozenset(s) key would drop the repeats and merge them, and sorted(s) on its own is a list, which a dict can't use as a key.
A lossy key: key on
"".join(sorted(s)), never onfrozenset(s)orset(s). A set drops repeated letters, so"aab"and"abb"would land in one group.An unhashable key:
sorted(s)returns a list, and a list can't be a dict key (TypeError: unhashable type). Join it into a string or wrap it intuple(...).A plain dict without a default:
groups[key].append(s)raisesKeyErroron the first word of each key unlessgroupsis adefaultdict(list)(or you usegroups.setdefault(key, [])).Dropping the empty word:
""is a real word whose key is"";[""]must return[[""]], not[].Comparing words pairwise: checking each word against every group already built is O(N^2) comparisons; the map's lookup makes each word one step.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Group the anagrams together" and "in any order": the answer is a set of buckets, and anagrams are exactly the words that look the same once their letters are sorted. Items that belong together because they share a key you can compute from each one: the Hash Map model. Turn each word into its key and let the map collect the words.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision per word: s joins the list stored under "".join(sorted(s)), or starts that list when the key is new; no word is ever compared with another.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
return list(groups.values()): the answer is the groups; returninggroupsor its keys gives the dict or the sorted keys such as"aet".
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Hash Map, keyed by a canonical form of each word. Two words are anagrams exactly when their sorted letters match, so I sort each word and join the letters back into a string: that's the key. The map sends each key to the list of words that produced it, so a single pass files every word with its anagrams, and I never compare two words with each other. The trap is a lossy key: it must keep every letter with its count, so a set of letters won't do, and it must be hashable, which is why I join the sorted list into a string. At the end I return the map's values. With N words of up to K letters, sorting dominates: O(N times K log K) time and O(N times K) space. For long words, a 26-slot letter count as the key removes the log factor.
Complexity & Mathematical Proof
O(N * K log K)
Look at the code: for s in strs runs N times. Inside, sorted(s) sorts at most K letters in O(K log K), "".join(...) builds a K-letter string in O(K), and groups[key].append(s) hashes that K-letter key in O(K) and appends in O(1) on average. Each word costs O(K log K), so the loop costs O(N * K log K). list(groups.values()) at the end touches each group once, O(N).
O(N * K)
Every distinct key is a string of up to K letters and there are at most N of them, so the keys take O(N * K). The lists in groups only hold references to the input words, one per word: O(N), and they are also the output. Each sorted(s) builds a temporary list of K letters, O(K), freed before the next word.
T = N · (O(K log K) sort + O(K) join + O(K) hash) = O(N · K log K)
Derivation Progression
N iterations
for s in strs handles each word exactly once.
O(K log K) + O(K) per word
sorted(s) sorts the word's letters; "".join(...) turns the list into a string.
O(K) per word, on average
groups[key] hashes the K-letter key once; .append(s) adds the word in O(1).
O(N · K log K)
The sort dominates each iteration; returning list(groups.values()) adds only O(N).
Variable Definitions
Number of words in strs (1 to 10^4)
Length of the longest word (0 to 100)
"".join(sorted(s)): the word's letters in alphabetical order
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N · K): up to N distinct keys of up to K letters, plus one O(K) sorted list at a time
O(N) references to the input words, grouped (not counted)
Boundary Best / Worst Cases
: every word has at most one letter, so each sort and each key is constant work
: every word has K = 100 letters
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
At scale the same signal reads "group records by a property computed from each one": deduplicating near-identical items, or bucketing log lines by their normalized template. Designing the key is the whole problem there: it must be exact, cheap to compute and small to store.
words of letters. Pairwise comparison is , about steps at the limits; one sorted key per word is , about .
At scale, the keys themselves cost memory (), and a skewed key (one huge group) turns into one hot bucket; when the words arrive as a stream or don't fit in memory, group in two passes: partition by hash(key) % P to disk, then group each partition.
Core Algorithmic State Invariants
- Groups Come Out in First-Seen Order
A Python dict keeps insertion order, so list(groups.values()) lists the groups in the order their first word appeared, each with its words in input order. LeetCode accepts any order, so nothing needs sorting.