Group Anagrams (LeetCode 49)
You will see how one hash map, keyed by each word's sorted letters, puts every anagram in the same group in a single pass.
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"]]strs = [""][[""]]strs = ["a"][["a"]]⚖️Formal Constraints & Bounds
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Why It Works & Core Invariant
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). |
Target: Group Anagrams (LeetCode 49). The question is "which words belong together?", so the value stored under each key is the list of words that share it; defaultdict starts an empty list the first time a key appears.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
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.
🪄 The Mathematical Harmony / Magic Trick
groups = defaultdict(list) # sorted letters -> wordsfor s in strs: key = "".join(sorted(s)) # "tea" -> "aet" groups[key].append(s) # one lookup per wordreturn list(groups.values()) 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.
💡 Summary
Pick the key that is equal exactly for the items that belong together, make it hashable, and let the map collect the items: one pass, one lookup per word, no pairwise comparisons.
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
You will see how a senior engineer turns "group the anagrams" into a choice of hash-map key, and names the one key that fails.
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
After each word s, groups[key] holds exactly the words read so far whose sorted letters equal key: a word joins the list stored under "".join(sorted(s)), or starts that list when the key is new.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
key = "".join(sorted(s)): the key must keep repeated letters.frozenset(s)orset(s)would put"aab"and"abb"in one group."".join(...):sorted(s)on its own is a list, and a list can't be a dict key (TypeError: unhashable type).groups[key].append(s): with a plaindictthe first word of every key raisesKeyError;defaultdict(list)starts the list.[""]: the empty word is a real word with key"", so the answer is[[""]], never[].
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. A set of letters throws away repeats and would merge "aab" with "abb", so the key must keep every letter with its count, 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.
So: the key is "".join(sorted(s)); groups[key].append(s) files each word; the trap is a key that drops repeated letters.
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)
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).
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
Triggers: "group the anagrams together", "in any order". Items belong together when a key computed from each one matches: Hash Map, keyed by the sorted letters, instead of comparing words pairwise.
words of letters. Pairwise comparison is , about steps at the limits; one sorted key per word is , about .
The key must be exact: frozenset(s) drops repeated letters and merges "aab" with "abb". 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
`key = "".join(sorted(s))` is equal for two words exactly when they are anagrams, so after each word `groups[key]` holds every word read so far that belongs with it.
Sorting keeps repeated letters, so `"aab"` and `"abb"` stay apart; `frozenset(s)` would merge them. Joining the sorted list into a string makes it usable as a dict key.
Each word costs one O(K log K) sort and one hash lookup, never a comparison with another word: O(N * K log K) time and O(N * K) space for the keys.
Group Anagrams (LeetCode 49)
You will see how one hash map, keyed by each word's sorted letters, puts every anagram in the same group in a single pass.
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"]]strs = [""][[""]]strs = ["a"][["a"]]⚖️Formal Constraints & Bounds
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Why It Works & Core Invariant
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). |
Target: Group Anagrams (LeetCode 49). The question is "which words belong together?", so the value stored under each key is the list of words that share it; defaultdict starts an empty list the first time a key appears.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
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.
🪄 The Mathematical Harmony / Magic Trick
groups = defaultdict(list) # sorted letters -> wordsfor s in strs: key = "".join(sorted(s)) # "tea" -> "aet" groups[key].append(s) # one lookup per wordreturn list(groups.values()) 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.
💡 Summary
Pick the key that is equal exactly for the items that belong together, make it hashable, and let the map collect the items: one pass, one lookup per word, no pairwise comparisons.
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
You will see how a senior engineer turns "group the anagrams" into a choice of hash-map key, and names the one key that fails.
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
After each word s, groups[key] holds exactly the words read so far whose sorted letters equal key: a word joins the list stored under "".join(sorted(s)), or starts that list when the key is new.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
key = "".join(sorted(s)): the key must keep repeated letters.frozenset(s)orset(s)would put"aab"and"abb"in one group."".join(...):sorted(s)on its own is a list, and a list can't be a dict key (TypeError: unhashable type).groups[key].append(s): with a plaindictthe first word of every key raisesKeyError;defaultdict(list)starts the list.[""]: the empty word is a real word with key"", so the answer is[[""]], never[].
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. A set of letters throws away repeats and would merge "aab" with "abb", so the key must keep every letter with its count, 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.
So: the key is "".join(sorted(s)); groups[key].append(s) files each word; the trap is a key that drops repeated letters.
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)
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).
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
Triggers: "group the anagrams together", "in any order". Items belong together when a key computed from each one matches: Hash Map, keyed by the sorted letters, instead of comparing words pairwise.
words of letters. Pairwise comparison is , about steps at the limits; one sorted key per word is , about .
The key must be exact: frozenset(s) drops repeated letters and merges "aab" with "abb". 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
`key = "".join(sorted(s))` is equal for two words exactly when they are anagrams, so after each word `groups[key]` holds every word read so far that belongs with it.
Sorting keeps repeated letters, so `"aab"` and `"abb"` stay apart; `frozenset(s)` would merge them. Joining the sorted list into a string makes it usable as a dict key.
Each word costs one O(K log K) sort and one hash lookup, never a comparison with another word: O(N * K log K) time and O(N * K) space for the keys.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| A hash map from the key the question is about to what the answer needs | groups: dict[str, list[str]] = defaultdict(list) | The question is "which words belong together?", so the value stored under each key is the list of words that share it; defaultdict starts an empty list the first time a key appears. |
| Visit every item once | for s in strs: | One pass over the words: each word is handled exactly once and never compared with another word. |
| Compute an exact key: equal for items that belong together, different for all others | key = "".join(sorted(s)) | Sorting puts any anagram's letters in the same order, repeats included; joining the list into a string makes it hashable. |
| Seen this key before? One lookup files the item | groups[key].append(s) | A known key adds the word to its group; a new key starts a group of one. |
| Read the answer out of the map | return list(groups.values()) | Each value is one complete group of anagrams; LeetCode accepts the groups and the words in any order. |