Hashing & Frequency Maps (Group Anagrams, Two Sum)
Group Anagrams (LC 49)(opens leetcode.com)
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.
"ate", "eat" and "tea" all sort to "aet"; "nat" and "tan" both sort to "ant"; nothing else sorts to "abt", so "bat" stands alone.Hash Map
items ➔ computed key ➔ dict lookup or count in O(1)| 1 | from collections import defaultdict |
| 2 | |
| 3 | |
| 4 | def group_anagrams(strs: list[str]) -> list[list[str]]: |
| 5 | """Group Anagrams: words with the same sorted letters share one key in a hash map. |
| 6 | Time: O(N * K log K) | Space: O(N * K) |
| 7 | """ |
| 8 | groups: dict[str, list[str]] = defaultdict(list) # key -> every word read so far with that key |
| 9 | # 1. File Each Word Under Its Key: |
| 10 | # Words with the same letters and the same counts produce the same sorted-letters key ("eat", "tea" -> "aet"), so every anagram lands in the same group without comparing any two words. |
| 11 | for s in strs: |
| 12 | key = "".join(sorted(s)) |
| 13 | groups[key].append(s) |
| 14 | return list(groups.values()) |
| 15 | |
| 16 | |
| 17 | def two_sum(nums: list[int], target: int) -> list[int]: |
| 18 | """Two Sum: remember each value's index, and look up the partner each new value needs. |
| 19 | Time: O(N) | Space: O(N) |
| 20 | """ |
| 21 | index_of: dict[int, int] = {} # value -> an index where it was seen |
| 22 | # 1. Look Up The Partner Before Storing: |
| 23 | # If target - num was already seen, its stored index completes the pair; storing num only after the lookup keeps num from ever pairing with itself. |
| 24 | for i, num in enumerate(nums): |
| 25 | partner = target - num |
| 26 | if partner in index_of: |
| 27 | return [index_of[partner], i] |
| 28 | index_of[num] = i |
| 29 | return [] # LeetCode guarantees exactly one answer, so this line is never reached |
groups[key] is precisely the words so far whose sorted letters equal key.A hash map finds a key's entry in one step, so pick the key the question is about and store under it what the answer needs: in group_anagrams the key is a word's sorted letters and the value is every word read so far with that key; in two_sum the key is a number and the value is its index. Items that belong together produce equal keys, so groups[key].append(s) files every anagram in one pass without comparing any two words, and partner in index_of finds an earlier number that completes the pair without a second loop. The trap is a lossy key: it must be equal only for items that truly belong together, so key on "".join(sorted(s)), which keeps repeated letters, never on frozenset(s) or set(s), which drop them and put "aab" and "abb" in one group.
See it run
Count and Lookup, step by step
key -groups 0
The top row is strs. The middle row is the key of each word. The bottom row is the number of the group that holds the word.
readthe word being read from strskeythe sorted letters of that wordfiledthe group number the word was added to
Start: groups is empty and strs has 6 words. Each word will get a key and a group number.
Gotcha 1 of 4
- The trap
Gotcha 1: Keying on
frozenset(s)instead of the sorted lettersMistakekey = frozenset(s)Fixkey = "".join(sorted(s))What happens: A set keeps each letter once and drops the repeats.
"aab"and"abb"both give the set ofaandb. They land in one group, but they are not anagrams."".join(sorted(s))keeps every letter, repeats included.Example: strs = ["aab", "abb"]Mistake: returns [['aab', 'abb']]Fix: returns [['aab'], ['abb']]
- The question counts contiguous subarrays with an exact sum, as in Subarray Sum Equals K (LC 560): the keys you look up are running sums of a prefix, not the items themselves. See Prefix Sum Map
Deep Dive
A hash map answers one question: where is this key?
A hash map is a table that finds the entry for a key in one step, on average. It does not scan the other entries. This is the only property the card uses.
The card's work is to choose the key. The key is whatever the question asks about. Two items that should be treated as the same must produce the same key. Two items that should be kept apart must produce different keys.
In group_anagrams the key is "".join(sorted(s)). Two words are anagrams exactly when they have the same letters with the same counts, and sorting the letters puts those letters in one fixed order. So anagrams get one key and all other words get another.
In two_sum the key is a number. index_of[num] is an index where that number was seen. For a new num, the question "which earlier number completes the pair?" becomes one lookup of partner = target - num.
Both functions read the input once. The map holds what was read so far, and each new item asks the map one question.
Group Anagrams, traced on six words
Take strs = ["aab", "eat", "abb", "tea", "baa", "ate"]. groups starts empty.
"aab" has the key "aab". The key is new, so group 1 starts with ["aab"]. "eat" has the key "aet", so group 2 starts. "abb" has the key "abb", which is different from "aab", so group 3 starts.
"tea" also has the key "aet", so it joins group 2. "baa" has the key "aab" and joins group 1. "ate" has the key "aet" and joins group 2.
The board also marks the trap after "aab". A set key would give "aab" and "abb" the same letters a and b, and the two words would share a group.
The result is [["aab", "baa"], ["eat", "tea", "ate"], ["abb"]]. No step compared two words with each other. Each word cost one sort and one map operation.
On the LeetCode example ["eat", "tea", "tan", "ate", "nat", "bat"], the same code returns [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].
The key must keep exactly the facts that matter
A key can fail in two ways. If it throws away a fact that matters, different items collide. If it keeps a fact that does not matter, equal items are split.
frozenset("aab") keeps the set of letters, {a, b}, and drops the counts. "abb" gives the same set, so the two words share a group although they are not anagrams. On ["aab", "abb"], the right answer is [["aab"], ["abb"]], and the set key returns [["aab", "abb"]].
sorted(s) keeps everything, but it returns a list. A list can change, so Python does not allow it as a dictionary key and raises a TypeError. Use "".join(sorted(s)) or tuple(sorted(s)).
A key made of 26 letter counts avoids sorting. Use tuple(count). If you join the counts into a string, add a separator, because "1" + "11" and "11" + "1" become the same text "111".
Cost, and the order of lookup and store in Two Sum
For group_anagrams, let N be the number of words and K the longest word length. Each word costs O(K log K) to sort, so the time is O(N * K log K). The map stores every word once, so the space is O(N * K). A count key replaces the sort with an O(K) pass, and the time becomes O(N * K).
For two_sum, each of the N numbers costs one lookup and one store. The time is O(N) and the space is O(N). The comparison is a double loop over all pairs, which costs O(N^2).
In two_sum, the lookup must come before the store. If index_of[num] = i runs first, partner in index_of can find num itself when partner == num. For nums = [3, 2, 4] and target = 6, the store-first code returns [0, 0] instead of [1, 2].
A repeated number is not a problem with the right order. For nums = [3, 3] and target = 6, the first 3 is stored at index 0. The second 3 looks up partner = 3 and finds index 0, so the result is [0, 1].
60-Second Pitch
"Comparing every pair of words costs O(N^2) comparisons, so I choose a key instead. Two words are anagrams when their sorted letters are equal, so "".join(sorted(s)) is the key, and I keep a dictionary from each key to its words. One pass reads each word, computes its key and appends it to groups[key]. No two words are compared. The time is O(N * K log K) for N words of length at most K, and the space is O(N * K). The key must keep the letter counts. A set of letters would merge "aab" and "abb". For Two Sum the same idea stores each number's index, and I look up the partner before I store the current number."
Common Questions
- Why is a hash map lookup
O(1)? The map turns a key into a position with a hash function and goes straight to that position. Different keys can share a position, but a good hash function keeps those collisions rare. So a lookup takes constant time on average. The worst case is
O(N)when many keys collide.- Why do you sort the letters to make the key?
Two words are anagrams when they have the same letters with the same counts. Sorting puts the letters in one fixed order, so every anagram of a word gives the same text, and any other word gives different text.
- How can Group Anagrams run without the sort?
Count the letters of each word in a list of 26 numbers and use
tuple(count)as the key. The pass over a word costsO(K)instead ofO(K log K), so the total time isO(N * K). The key is a tuple because a list cannot be a dictionary key.- What changes in Two Sum if the numbers are sorted?
Use two pointers, one at each end of the sorted list. They need
O(1)extra space and the sameO(N)time. The hash map costsO(N)space, but it also works on unsorted input, which is what Two Sum (LC 1) gives you.- How do you count items instead of grouping them?
Store a number as the value instead of a list.
counts[key] += 1for each item gives the frequency of every key in one pass. Valid Anagram (LC 242) compares two such count tables.
SWE Reasoning
Spot it
- The question asks "have I seen this before?", "how many of each?" or "which items belong together?" (Group Anagrams (LC 49), Contains Duplicate (LC 217)).
- A partner that completes a target can be named from the current item, as in Two Sum (LC 1).
- Items that belong together can be given an equal key, computed from the item alone.
- A double loop over all pairs is the obvious answer, and it is too slow.
The invariant, step by step
groupsstarts empty. It maps a key to every word read so far that has that key.- For each word
s, computekey = "".join(sorted(s)). The key depends only on the letters and their counts. groups[key].append(s)adds the word to the right group. A new key creates a new group.- After each word,
groups[key]holds exactly the words so far whose sorted letters equalkey. - After the last word,
list(groups.values())is the answer. No two words were compared with each other.
Traps
- A key that drops information.
frozenset(s)puts"aab"and"abb"in one group, because it forgets the letter counts. - A key that cannot be stored.
sorted(s)is a list, and a list raises aTypeErroras a dictionary key. - Store before lookup in
two_sum.index_of[num] = ibefore the lookup lets a number pair with itself. The calltwo_sum([3, 2, 4], 6)returns[0, 0]. - Count keys joined with no separator. One
awith elevenbletters and elevenaletters with onebgive the same text.
Practice
Hashing & Frequency Maps (Group Anagrams, Two Sum)
Group Anagrams (LC 49)(opens leetcode.com)
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.
"ate", "eat" and "tea" all sort to "aet"; "nat" and "tan" both sort to "ant"; nothing else sorts to "abt", so "bat" stands alone.Hash Map
items ➔ computed key ➔ dict lookup or count in O(1)| 1 | from collections import defaultdict |
| 2 | |
| 3 | |
| 4 | def group_anagrams(strs: list[str]) -> list[list[str]]: |
| 5 | """Group Anagrams: words with the same sorted letters share one key in a hash map. |
| 6 | Time: O(N * K log K) | Space: O(N * K) |
| 7 | """ |
| 8 | groups: dict[str, list[str]] = defaultdict(list) # key -> every word read so far with that key |
| 9 | # 1. File Each Word Under Its Key: |
| 10 | # Words with the same letters and the same counts produce the same sorted-letters key ("eat", "tea" -> "aet"), so every anagram lands in the same group without comparing any two words. |
| 11 | for s in strs: |
| 12 | key = "".join(sorted(s)) |
| 13 | groups[key].append(s) |
| 14 | return list(groups.values()) |
| 15 | |
| 16 | |
| 17 | def two_sum(nums: list[int], target: int) -> list[int]: |
| 18 | """Two Sum: remember each value's index, and look up the partner each new value needs. |
| 19 | Time: O(N) | Space: O(N) |
| 20 | """ |
| 21 | index_of: dict[int, int] = {} # value -> an index where it was seen |
| 22 | # 1. Look Up The Partner Before Storing: |
| 23 | # If target - num was already seen, its stored index completes the pair; storing num only after the lookup keeps num from ever pairing with itself. |
| 24 | for i, num in enumerate(nums): |
| 25 | partner = target - num |
| 26 | if partner in index_of: |
| 27 | return [index_of[partner], i] |
| 28 | index_of[num] = i |
| 29 | return [] # LeetCode guarantees exactly one answer, so this line is never reached |
groups[key] is precisely the words so far whose sorted letters equal key.A hash map finds a key's entry in one step, so pick the key the question is about and store under it what the answer needs: in group_anagrams the key is a word's sorted letters and the value is every word read so far with that key; in two_sum the key is a number and the value is its index. Items that belong together produce equal keys, so groups[key].append(s) files every anagram in one pass without comparing any two words, and partner in index_of finds an earlier number that completes the pair without a second loop. The trap is a lossy key: it must be equal only for items that truly belong together, so key on "".join(sorted(s)), which keeps repeated letters, never on frozenset(s) or set(s), which drop them and put "aab" and "abb" in one group.
See it run
Count and Lookup, step by step
key -groups 0
The top row is strs. The middle row is the key of each word. The bottom row is the number of the group that holds the word.
readthe word being read from strskeythe sorted letters of that wordfiledthe group number the word was added to
Start: groups is empty and strs has 6 words. Each word will get a key and a group number.
Gotcha 1 of 4
- The trap
Gotcha 1: Keying on
frozenset(s)instead of the sorted lettersMistakekey = frozenset(s)Fixkey = "".join(sorted(s))What happens: A set keeps each letter once and drops the repeats.
"aab"and"abb"both give the set ofaandb. They land in one group, but they are not anagrams."".join(sorted(s))keeps every letter, repeats included.Example: strs = ["aab", "abb"]Mistake: returns [['aab', 'abb']]Fix: returns [['aab'], ['abb']]
- The question counts contiguous subarrays with an exact sum, as in Subarray Sum Equals K (LC 560): the keys you look up are running sums of a prefix, not the items themselves. See Prefix Sum Map
Deep Dive
A hash map answers one question: where is this key?
A hash map is a table that finds the entry for a key in one step, on average. It does not scan the other entries. This is the only property the card uses.
The card's work is to choose the key. The key is whatever the question asks about. Two items that should be treated as the same must produce the same key. Two items that should be kept apart must produce different keys.
In group_anagrams the key is "".join(sorted(s)). Two words are anagrams exactly when they have the same letters with the same counts, and sorting the letters puts those letters in one fixed order. So anagrams get one key and all other words get another.
In two_sum the key is a number. index_of[num] is an index where that number was seen. For a new num, the question "which earlier number completes the pair?" becomes one lookup of partner = target - num.
Both functions read the input once. The map holds what was read so far, and each new item asks the map one question.
Group Anagrams, traced on six words
Take strs = ["aab", "eat", "abb", "tea", "baa", "ate"]. groups starts empty.
"aab" has the key "aab". The key is new, so group 1 starts with ["aab"]. "eat" has the key "aet", so group 2 starts. "abb" has the key "abb", which is different from "aab", so group 3 starts.
"tea" also has the key "aet", so it joins group 2. "baa" has the key "aab" and joins group 1. "ate" has the key "aet" and joins group 2.
The board also marks the trap after "aab". A set key would give "aab" and "abb" the same letters a and b, and the two words would share a group.
The result is [["aab", "baa"], ["eat", "tea", "ate"], ["abb"]]. No step compared two words with each other. Each word cost one sort and one map operation.
On the LeetCode example ["eat", "tea", "tan", "ate", "nat", "bat"], the same code returns [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].
The key must keep exactly the facts that matter
A key can fail in two ways. If it throws away a fact that matters, different items collide. If it keeps a fact that does not matter, equal items are split.
frozenset("aab") keeps the set of letters, {a, b}, and drops the counts. "abb" gives the same set, so the two words share a group although they are not anagrams. On ["aab", "abb"], the right answer is [["aab"], ["abb"]], and the set key returns [["aab", "abb"]].
sorted(s) keeps everything, but it returns a list. A list can change, so Python does not allow it as a dictionary key and raises a TypeError. Use "".join(sorted(s)) or tuple(sorted(s)).
A key made of 26 letter counts avoids sorting. Use tuple(count). If you join the counts into a string, add a separator, because "1" + "11" and "11" + "1" become the same text "111".
Cost, and the order of lookup and store in Two Sum
For group_anagrams, let N be the number of words and K the longest word length. Each word costs O(K log K) to sort, so the time is O(N * K log K). The map stores every word once, so the space is O(N * K). A count key replaces the sort with an O(K) pass, and the time becomes O(N * K).
For two_sum, each of the N numbers costs one lookup and one store. The time is O(N) and the space is O(N). The comparison is a double loop over all pairs, which costs O(N^2).
In two_sum, the lookup must come before the store. If index_of[num] = i runs first, partner in index_of can find num itself when partner == num. For nums = [3, 2, 4] and target = 6, the store-first code returns [0, 0] instead of [1, 2].
A repeated number is not a problem with the right order. For nums = [3, 3] and target = 6, the first 3 is stored at index 0. The second 3 looks up partner = 3 and finds index 0, so the result is [0, 1].
60-Second Pitch
"Comparing every pair of words costs O(N^2) comparisons, so I choose a key instead. Two words are anagrams when their sorted letters are equal, so "".join(sorted(s)) is the key, and I keep a dictionary from each key to its words. One pass reads each word, computes its key and appends it to groups[key]. No two words are compared. The time is O(N * K log K) for N words of length at most K, and the space is O(N * K). The key must keep the letter counts. A set of letters would merge "aab" and "abb". For Two Sum the same idea stores each number's index, and I look up the partner before I store the current number."
Common Questions
- Why is a hash map lookup
O(1)? The map turns a key into a position with a hash function and goes straight to that position. Different keys can share a position, but a good hash function keeps those collisions rare. So a lookup takes constant time on average. The worst case is
O(N)when many keys collide.- Why do you sort the letters to make the key?
Two words are anagrams when they have the same letters with the same counts. Sorting puts the letters in one fixed order, so every anagram of a word gives the same text, and any other word gives different text.
- How can Group Anagrams run without the sort?
Count the letters of each word in a list of 26 numbers and use
tuple(count)as the key. The pass over a word costsO(K)instead ofO(K log K), so the total time isO(N * K). The key is a tuple because a list cannot be a dictionary key.- What changes in Two Sum if the numbers are sorted?
Use two pointers, one at each end of the sorted list. They need
O(1)extra space and the sameO(N)time. The hash map costsO(N)space, but it also works on unsorted input, which is what Two Sum (LC 1) gives you.- How do you count items instead of grouping them?
Store a number as the value instead of a list.
counts[key] += 1for each item gives the frequency of every key in one pass. Valid Anagram (LC 242) compares two such count tables.
SWE Reasoning
Spot it
- The question asks "have I seen this before?", "how many of each?" or "which items belong together?" (Group Anagrams (LC 49), Contains Duplicate (LC 217)).
- A partner that completes a target can be named from the current item, as in Two Sum (LC 1).
- Items that belong together can be given an equal key, computed from the item alone.
- A double loop over all pairs is the obvious answer, and it is too slow.
The invariant, step by step
groupsstarts empty. It maps a key to every word read so far that has that key.- For each word
s, computekey = "".join(sorted(s)). The key depends only on the letters and their counts. groups[key].append(s)adds the word to the right group. A new key creates a new group.- After each word,
groups[key]holds exactly the words so far whose sorted letters equalkey. - After the last word,
list(groups.values())is the answer. No two words were compared with each other.
Traps
- A key that drops information.
frozenset(s)puts"aab"and"abb"in one group, because it forgets the letter counts. - A key that cannot be stored.
sorted(s)is a list, and a list raises aTypeErroras a dictionary key. - Store before lookup in
two_sum.index_of[num] = ibefore the lookup lets a number pair with itself. The calltwo_sum([3, 2, 4], 6)returns[0, 0]. - Count keys joined with no separator. One
awith elevenbletters and elevenaletters with onebgive the same text.