beta

2.2 Hashing · cheat sheet

Counting and grouping.

Count with a map, and group items by a computed key such as sorted letters, a signature or a bucket.

Spot it: the words in the question

group the items that share
same letters in any order
count how often each
one group for each hour
put together what belongs together
a key computed from the item

The invariant

After i items are read, each group holds the positions of the items that share its key, in increasing order, and no two groups share a key.

The pattern

Pattern cardCounting and grouping

Use it when you must put together the items that belong together, or count how many items share a property. Signal words: group the items that share, the same letters in any order, one group for each hour, how many of each.

Start: an empty map from key to a count, or from key to a group, plus the list of groups in the order they start.

Step: compute the key of the current item. Look it up. If it is new, start the entry. Then add one to the count, or append the position to the group.

Stop: when the items run out.

It does not find items that are close but not equal. One key answers "are these two items equal under the key?".

Cost: O(n) map steps on average, plus the cost of computing and hashing one key for each item. For n words of L letters with a sorted key, that is O(n × L log L) in all. The comparison of every pair costs O(n^2) comparisons.

Complexity

Time. The pass reads each item once, builds one key and makes one lookup and at most one insert. A key is not free: sorting the L letters of a word costs about L log L steps. Hashing the key and checking it against its bucket costs about L more, so the whole pass is O(n × L log L).
At scale. For 100,000 words of 8 letters, the sorting is about 100,000 × 24, or 2.4 million, steps. The pair scan needs about 5 × 10^9 comparisons, and each of them sorts two words.
Worst case. If many keys land in one bucket, each lookup walks a long chain, as the first lesson showed. A good hash and a resizing table keep this rare.
Space. The map holds one entry for each different key, and the groups hold every position once. That is O(n) entries, plus the keys themselves, which take up to n × L letters.
Trade. The pair scan stores almost nothing extra. The map stores one key for each group. That memory buys the drop from billions of comparisons to millions of steps.

Templates · Python

The lesson’s templates, checked in all four languages against the same test cases.

Code in four languagesCount by key: the size of the biggest group

pythonbiggest_group · 13 lines

def biggest_group(words):
    # [1] A map from each key to how many words have it.
    counts = {}
    best = 0
    # [2] Read each word once.
    for word in words:
        # [3] The key: the letters of the word in sorted order. Words with the same letters share it.
        key = "".join(sorted(word))
        # [4] Add one to the count of that key, and keep the largest count seen.
        counts[key] = counts.get(key, 0) + 1
        best = max(best, counts[key])
    # [5] The size of the biggest group, or 0 for an empty list.
    return best

java18 lines

public int biggestGroup(String[] words) {
    // [1] A map from each key to how many words have it.
    java.util.HashMap<String, Integer> counts = new java.util.HashMap<>();
    int best = 0;
    // [2] Read each word once.
    for (String word : words) {
        // [3] The key: the letters of the word in sorted order. Words with the same letters share it.
        char[] letters = word.toCharArray();
        java.util.Arrays.sort(letters);
        String key = new String(letters);
        // [4] Add one to the count of that key, and keep the largest count seen.
        int count = counts.getOrDefault(key, 0) + 1;
        counts.put(key, count);
        best = Math.max(best, count);
    }
    // [5] The size of the biggest group, or 0 for an empty list.
    return best;
}

c++16 lines

int biggestGroup(vector<string>& words) {
    // [1] A map from each key to how many words have it.
    unordered_map<string, int> counts;
    int best = 0;
    // [2] Read each word once.
    for (const string& word : words) {
        // [3] The key: the letters of the word in sorted order. Words with the same letters share it.
        string key = word;
        sort(key.begin(), key.end());
        // [4] Add one to the count of that key, and keep the largest count seen.
        int count = ++counts[key];
        best = max(best, count);
    }
    // [5] The size of the biggest group, or 0 for an empty list.
    return best;
}

javascriptbiggestGroup · 16 lines

function biggestGroup(words) {
  // [1] A map from each key to how many words have it.
  const counts = new Map();
  let best = 0;
  // [2] Read each word once.
  for (const word of words) {
    // [3] The key: the letters of the word in sorted order. Words with the same letters share it.
    const key = word.split("").sort().join("");
    // [4] Add one to the count of that key, and keep the largest count seen.
    const count = (counts.get(key) ?? 0) + 1;
    counts.set(key, count);
    best = Math.max(best, count);
  }
  // [5] The size of the biggest group, or 0 for an empty list.
  return best;
}

Code in four languagesGroup by key: the positions of the words that share their letters

pythongroup_words · 15 lines

def group_words(words):
    # [1] A map from each key to its group number, and the groups in the order they started.
    index_of = {}
    groups = []
    for i in range(len(words)):
        # [2] The key: the letters of the word in sorted order. Words with the same letters share it.
        key = "".join(sorted(words[i]))
        # [3] The first word with a new key starts a new group.
        if key not in index_of:
            index_of[key] = len(groups)
            groups.append([])
        # [4] Add this position to the group of its key.
        groups[index_of[key]].append(i)
    # [5] The groups, in the order they started.
    return groups

java24 lines

public int[][] groupWords(String[] words) {
    // [1] A map from each key to its group number, and the groups in the order they started.
    java.util.HashMap<String, Integer> indexOf = new java.util.HashMap<>();
    java.util.List<java.util.List<Integer>> groups = new java.util.ArrayList<>();
    for (int i = 0; i < words.length; i++) {
        // [2] The key: the letters of the word in sorted order. Words with the same letters share it.
        char[] letters = words[i].toCharArray();
        java.util.Arrays.sort(letters);
        String key = new String(letters);
        // [3] The first word with a new key starts a new group.
        if (!indexOf.containsKey(key)) {
            indexOf.put(key, groups.size());
            groups.add(new java.util.ArrayList<>());
        }
        // [4] Add this position to the group of its key.
        groups.get(indexOf.get(key)).add(i);
    }
    // [5] The groups, in the order they started.
    int[][] result = new int[groups.size()][];
    for (int g = 0; g < groups.size(); g++) {
        result[g] = groups.get(g).stream().mapToInt(Integer::intValue).toArray();
    }
    return result;
}

c++19 lines

vector<vector<int>> groupWords(vector<string>& words) {
    // [1] A map from each key to its group number, and the groups in the order they started.
    unordered_map<string, int> indexOf;
    vector<vector<int>> groups;
    for (int i = 0; i < (int)words.size(); i++) {
        // [2] The key: the letters of the word in sorted order. Words with the same letters share it.
        string key = words[i];
        sort(key.begin(), key.end());
        // [3] The first word with a new key starts a new group.
        if (!indexOf.count(key)) {
            indexOf[key] = groups.size();
            groups.push_back({});
        }
        // [4] Add this position to the group of its key.
        groups[indexOf[key]].push_back(i);
    }
    // [5] The groups, in the order they started.
    return groups;
}

javascriptgroupWords · 18 lines

function groupWords(words) {
  // [1] A map from each key to its group number, and the groups in the order they started.
  const indexOf = new Map();
  const groups = [];
  for (let i = 0; i < words.length; i++) {
    // [2] The key: the letters of the word in sorted order. Words with the same letters share it.
    const key = words[i].split("").sort().join("");
    // [3] The first word with a new key starts a new group.
    if (!indexOf.has(key)) {
      indexOf.set(key, groups.length);
      groups.push([]);
    }
    // [4] Add this position to the group of its key.
    groups[indexOf.get(key)].push(i);
  }
  // [5] The groups, in the order they started.
  return groups;
}

Pitfalls

✕ 1The sum of the letters as the key
This version adds up the position of each letter in the alphabet, with a = 1, b = 2 and so on, and uses the sum as the key. It is quick to compute, but different words can have the same sum.
✕ 2The set of letters as the key
This version uses the set of distinct letters as the key. Two words with the same letters in different numbers share a set.
✕ 3The sorted array as the key
In Java, the key is the sorted char[] itself, with no conversion to a String. An array compares by identity, so two arrays with equal letters are two different keys. In JavaScript, a Map also compares an array key by identity. In Python, a list key raises an error, because a list cannot be hashed.
✕ 4Letter counts glued together
This version uses the faster key from Variation 3, the count of each of the 26 letters, and writes the counts one after another with nothing between them.

Test these

An empty dictionary
The same word twice
Repeated letters
Capital letters

Not this pattern

Words that are close, not equal

Your team lead asks for the words that are one letter away from each other, such as cat and cot. A key says whether two words are equal under a rule. Cat and cot have different sorted letters, so no single key puts them together.

Practise it

systemdesignmastery.dev/dsa/cheatsheets/grouping