Watch 10 video solutions for Group Anagrams, a medium level problem involving Array, Hash Table, String. This walkthrough by NeetCode has 812,823 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
"bat"."nat" and "tan" are anagrams as they can be rearranged to form each other."ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] consists of lowercase English letters.Problem Overview: You receive an array of strings and must group words that are anagrams of each other. Two strings belong in the same group if they contain the same characters with the same frequency, regardless of order.
Approach 1: Hash Map + Character Frequency (O(n * k))
This method builds a frequency signature for every string. For each word, count how many times each letter appears using a fixed-size array of length 26. Convert that frequency array into a hashable key (for example a tuple or string) and store the word in a hash map where the key represents the character distribution. Words with identical frequency signatures are anagrams and end up in the same bucket.
The key insight: anagrams share identical character counts. Instead of sorting characters, you directly encode the frequency of each letter. Each string requires a single pass to build its signature, giving O(n * k) time where n is the number of strings and k is the average string length. Space complexity is O(n * k) due to storing grouped strings in the map. This approach heavily relies on a hash table for constant-time grouping.
Approach 2: Sorting Characters as Key (O(n * k log k))
A simpler and very common solution sorts each string alphabetically and uses the sorted string as the key in a hash map. For example, "eat", "tea", and "ate" all become "aet" after sorting. When you iterate through the input, sort the characters of each word, then append the original word to the list stored under that sorted key.
This approach is easy to implement and works well for interview settings. Sorting each word takes O(k log k), so the total runtime becomes O(n * k log k). Space complexity remains O(n * k) for storing groups and keys. It combines string manipulation with sorting and hash-based grouping.
Recommended for interviews: The sorting-based hash map approach is the most widely expected solution because it is concise and easy to reason about. Many candidates start there. The frequency-count approach is more optimal asymptotically since it avoids sorting and runs in O(n * k). Showing both approaches demonstrates solid understanding of hashing, string manipulation, and algorithmic tradeoffs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map + Character Frequency | O(n * k) | O(n * k) | When optimizing runtime and alphabet size is fixed (e.g., lowercase letters) |
| Hash Map + Sorted String Key | O(n * k log k) | O(n * k) | General interview solution; simplest and most commonly implemented |