Hashing
Group by a signature
Why it matters
Search indexes, media libraries, and data-cleaning jobs often need to group equivalent items while preserving the originals. Comparing each new item with every group becomes quadratic when most items differ. The solution must classify each word once without testing it against every group already formed.
Example
Group Anagrams
Group the strings in strs that are anagrams of one another. Sort characters inside each group lexicographically, then sort the groups by their first string so the answer is deterministic.
- Input
- strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
- Output
- [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Group Anagrams
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]→[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
The baseline, Compare each word with each group, is O(n² · k log k) · O(n · k). The better model below keeps this exact input and removes that bottleneck.
"eat", "tea", and "ate" in the example all become "aet". Instead of comparing each new word with every existing group, compute that shared signature once and use it to select the group directly.
In ["eat", "tea", "tan", "ate", "nat", "bat"], sorting the letters gives keys "aet", "aet", "ant", "aet", "ant", and "abt". Anagrams receive the same key because they contain the same letters with the same counts.
groups maps each key to a list. Processing the six words builds "aet" → ["eat", "tea", "ate"], "ant" → ["tan", "nat"], and "abt" → ["bat"]. The dictionary chooses a list from the key, while each list keeps the input words unchanged.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.