Hashing · Stage 3 of 3
Grouping by Canonical Key
Turn each item into a signature so the map gathers matches for you
Foundations
So far, each lookup asked about one exact value: whether it was seen, and where. What if items that look different should count as the same, and you want them gathered together?
A canonical key is a standard form that every equivalent item reduces to. Sorting is one way to get it: [3, 1, 2] and [2, 3, 1] both sort to (1, 2, 3), so they share a key. A map from key to list then files each item with one O(1) lookup, and the items themselves stay unchanged inside the lists.
Take nums = [7, 1, 5, 3, 6] and group the values by x % 2, odd or even. The key for 7, 1, 5, and 3 is 1, and the key for 6 is 0, so one pass leaves {1: [7, 1, 5, 3], 0: [6]}. Choosing the key is the whole design: it must be equal for exactly the items you want together.
nums
x % 2 sends 7, 1, 5, and 3 to key 1 and 6 to key 0. Each value cost one lookup.Case Scenario
The problem
Group Anagrams
Group the strings in strs that are anagrams of one another. Sort the strings 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"]]
Group Anagrams needs that key for words. Two words are anagrams when they use the same letters the same number of times, so sorting a word's letters gives its canonical key: "eat", "tea", and "ate" all sort to "aet". The answer is the map's lists: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].
Without a key, each word is compared with every group formed so far, checking whether their letters match. When most words start their own group, that is about n²/2 comparisons, each costing a sort of k letters, O(k log k). Most of those comparisons fail, and each new word repeats them against the same groups.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.