Coding Interview PatternsGroup Anagrams
MediumHash Maps
Group Anagrams
Explanation & Solution
Description
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.
Input:strs = ["eat","tea","tan","ate","nat","bat"]
0
eat
1
tea
2
tan
3
ate
4
nat
5
bat
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation: The strings "eat", "tea", and "ate" are anagrams. "tan" and "nat" are anagrams. "bat" has no anagram in the list.
Constraints
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Approach
Hash Maps pattern
1. Create a Hash Map for Grouping
- Initialize a
Mapwhere each key is a sorted version of a string, and the value is an array of strings that share that sorted form - All anagrams, when sorted character-by-character, produce the same key
2. Iterate and Categorize
- For each string in
strs: - Sort its characters to create the key (e.g., "eat" → "aet", "tea" → "aet")
- If the key does not exist in the map, create an empty array
- Push the original string into the array for that key
3. Collect the Groups
- Extract all values from the map — each value is a group of anagrams
- Sort each group and sort the groups themselves for consistent output
- Return the array of groups
Key Insight
- The fundamental insight is that anagrams are identical when sorted — sorting the characters of a string produces a canonical form that can be used as a hash map key
- An alternative to sorting each string is using a character frequency count as the key, which reduces per-string cost from O(k log k) to O(k)
Time
O(n * k log k) where n is the number of strings and k is the maximum string lengthSpace
O(n * k)storing all strings in the map