Group Anagrams
Problem
Given an array of strings strs, group the anagrams together. You may return the answer in any order.
- 1 ≤ strs.length ≤ 10⁴
- 0 ≤ strs[i].length ≤ 100
- strs[i] consists of lowercase English letters.
Example
strs = ["eat","tea","tan","ate","nat","bat"][["eat","tea","ate"],["tan","nat"],["bat"]]The brute-force approach would compare each string with every other string to check if they are anagrams, resulting in O(n^2 * k log k) time complexity (where n is number of strings and k is max string length). Instead, the algorithm sorts each string to create a canonical key representing its character composition. For example, "eat", "tea", and "ate" all sort to "aet". Using this key, the algorithm groups all anagrams together in a hash map. Iterating through the input, it appends each string to the list corresponding to its sorted key. Finally, it returns all grouped values. This approach reduces the complexity significantly by avoiding repeated pairwise comparisons.
Approach
Straightforward Solution
A brute-force approach compares every pair of strings to check if they are anagrams by sorting or counting characters, resulting in O(n^2 * k log k) time complexity, which is inefficient for large inputs.
Core Observation
Anagrams share the same characters in the same frequency, so sorting a string produces a unique canonical representation for all its anagrams.
Path to Optimal
Recognizing that sorting each string yields a canonical key that uniquely identifies its anagram group allows grouping strings by this key in a hash map. This transforms the problem from pairwise comparisons to a single pass with O(n * k log k) time complexity, where n is the number of strings and k is the max string length.
Optimal Approach
Iterate through each string, sort it to get the key, and append the original string to the list in a hash map keyed by the sorted string. After processing all strings, return the values of the hash map as the grouped anagrams.
Time
O(n * k log k)
Each of the n strings is sorted, which takes O(k log k) time where k is the maximum length of a string. Hash map insertions and lookups are O(1) on average, so total time is dominated by sorting each string.
Space
O(n * k)
The hash map stores all n strings grouped by their sorted keys. Each key and string requires space proportional to k, so total auxiliary space is O(n * k). This space is necessary to store the output groups.
Pattern Spotlight
Hash Maps (Grouping by Canonical Key)
When grouping items by an equivalence relation that can be represented as a unique key (like sorted characters for anagrams), use a hash map keyed by that canonical form to achieve efficient grouping in a single pass.
Solution
| 1 | from collections import defaultdict
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
|
| 5 | anagram_map = defaultdict(list)
|
| 6 | for s in strs:
|
| 7 | sorted_s = "".join(sorted(s))
|
| 8 | anagram_map[sorted_s].append(s)
|
| 9 | return list(anagram_map.values()) |
Step-by-Step Solution
Build Hash Map Grouping Strings by Sorted Key
| 5 | anagram_map = defaultdict(list)
|
| 6 | for s in strs:
|
| 7 | sorted_s = "".join(sorted(s))
|
| 8 | anagram_map[sorted_s].append(s)
|
Objective
To create a hash map that groups strings by their sorted character sequence.
Key Insight
Sorting each string produces a canonical key that uniquely identifies its anagram group. Using a hash map keyed by this sorted string allows efficient grouping in a single pass without pairwise comparisons. This leverages the fact that anagrams share identical sorted forms.
Interview Quick-Check
Core Logic
Sort each string to generate a canonical key and use it to group all anagrams together in a hash map.
State & Boundaries
Iterate through all strings exactly once, ensuring O(n) passes over the input.
Common Pitfalls & Bugs
Forgetting to convert the sorted list of characters back to a string before using it as a hash map key can cause errors.
Complexity
Sorting each string dominates the time complexity, so optimizing string sorting or using counting sort for fixed alphabets can improve performance.
Return Grouped Anagrams as List of Lists
| 9 | return list(anagram_map.values()) |
Objective
To extract and return all grouped anagrams from the hash map as a list of lists.
Key Insight
The hash map's values are lists of strings that are anagrams. Converting these values to a list returns the desired grouping. This step finalizes the grouping process by transforming the internal data structure into the required output format.
Interview Quick-Check
Core Logic
Return the values of the hash map, which represent all grouped anagrams.
State & Boundaries
Ensure the output format matches the problem requirement: a list of lists of strings.
Line Analysis
This solution has 1 Critical line interviewers watch for.
sorted_s = "".join(sorted(s))Sort the characters of the current string to form the canonical key.
Sorting transforms any anagram into the same canonical form, enabling grouping by identical keys in the hash map.
anagram_map = defaultdict(list)Initialize a default dictionary to group strings by their sorted keys.
Using a defaultdict with list values allows appending strings to groups without explicit key existence checks, simplifying code and ensuring O(1) average insertion time.
anagram_map[sorted_s].append(s)Append the original string to the list corresponding to its sorted key in the hash map.
This step groups all anagrams together by their sorted key, building the final grouping structure in a single pass.
return list(anagram_map.values())Return the list of all grouped anagrams from the hash map values.
Extracting the hash map's values as a list produces the required output format, completing the grouping process.
for s in strs:Iterate over each string in the input list.
Processing each string exactly once ensures the algorithm runs in linear time relative to the number of strings, which is essential for efficiency.
Test Your Understanding
Why is sorting each string an effective way to identify its anagram group?
Because all anagrams share the same characters in the same frequency, sorting rearranges them into the same canonical order, producing an identical key for all anagrams.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Group Anagrams from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Start drilling Group Anagrams for free