Counting and grouping

In this lesson you learn to count how often things occur, and to put things that belong together into one group, in a single pass. You compute a key for each item, and a hash table collects everything that shares a key.

The rewards tab of a payments app has a daily word puzzle. Each puzzle shows a clue word. Players earn a reward for every dictionary word that uses exactly the same letters, for example listen, silent and tinsel.

Your team lead says: Before the game starts, group the whole dictionary by letters, so that each puzzle knows its full answer set.

The dictionary holds 100,000 words, and the groups are rebuilt every time the word list changes.

Here is a short test: ["listen", "tinsel", "stone", "notes", "silent", "onset", "apple"]. The answer is the positions of the words in each group: positions 0, 1 and 4, then positions 2, 3 and 5, then position 6 on its own.

So the task is this: put the words that use the same letters into one group, without comparing every pair of words.

Before you write code, solve the test by hand. It shows how much work one rebuild takes.

You write the words in a row. You take each word that is not in a group yet, and compare it with every later word that is not in a group yet. Two words belong together when their letters, in sorted order, are equal.

The first attempt#

You turn the hand method into code.

Start with a correct version. For each word that is not in a group yet, compare it with every later word, and collect the words that match.

def group_words(words):
    groups = []
    placed = [False] * len(words)
    for i in range(len(words)):
        if placed[i]:
            continue
        group = [i]
        for j in range(i + 1, len(words)):  # every later word
            if not placed[j] and sorted(words[i]) == sorted(words[j]):
                group.append(j)
                placed[j] = True
        groups.append(group)
    return groups

This is correct. It makes up to n × (n − 1) / 2 comparisons: O(n^2). Each comparison also sorts two words. The team keeps it as the reference.

The scale check#

Now check the real dictionary.

A real dictionary holds 100,000 words, and the groups are rebuilt every time the word list changes.

Here is the count:

• Comparisons: 100,000 × 99,999 / 2, which is about 5 × 10^9.
• Time: at about 10^8 simple steps a second, that is about 50 seconds if each comparison cost one step.
• Each comparison sorts two words, so it costs many steps and the real time is longer still.

So a rebuild takes about a minute or more, and the puzzle cannot refresh its groups quickly.

The first attempt is correct, but it looks at pairs, and there are far too many pairs. Now the team looks for a way to avoid them.

Can we do better?#

Start with a simpler question. How many times does each value appear in a list?

Keep a hash table from value to count. For each value, add one to its count, starting from 0. This is the whole job in one line:

counts[value] = counts.get(value, 0) + 1

One lookup in a hash table takes one step on average, so counting n values takes n steps. A value that is not in the table has the count 0. This line is the heart of the lesson.

Now the puzzle. Listen, silent and tinsel are different words, so a table of word counts does not put them together. Their letters in sorted order are equal, though: all three become eilnst, and stone, notes and onset all become enost.

Words that use the same letters in a different order are called anagrams. The sorted string is the key. It is a computed key: you work it out from the word, and you do not store it in the word. It is the same for every anagram, and it differs for any word with other letters, so it is exactly the rule that decides who belongs together.

Now the table does the grouping. For each word:

1. Compute its key, the letters in sorted order.
2. If the key is new, start a new group for it.
3. Add the position of the word to the group of its key.

Seven words cost 7 keys and 7 lookups. The pair scan made 9 comparisons here, and up to 21 in the worst case.

Counting and grouping are the same move. When you count, the table stores a number, and you add one. When you group, the table stores a list, and you append the position. In both, the key decides which entry to change.

The race counts the worst case, where no two words share letters, so the pair scan compares every pair. At 10,000 words the pair scan makes 49,995,000 comparisons. The map makes 20,000 operations, one key and one lookup for each word. That is about 2,500 times less, and the gap grows with n.

Here is the rule that keeps both templates correct. Every line exists to protect it.

At the start no item is read and there are no groups, so the rule holds. Say it holds after i items. Look at the next item and its key.

If the key is in the map, the item joins that group. Its position is the largest so far, so the positions stay in increasing order. If not, it starts a new group with a key that no other group has.

So two items end up in one group exactly when their keys are equal. The groups come out in the order they started, because the list of groups only grows at the end.

Template 1: count by key#

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

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;
}

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;
}

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;
}

Template 2: group by key#

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

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;
}

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;
}

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;
}

Complexity in plain words#

• 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.

Edge cases#

Real production data brings edge cases.

The mistake museum#

When the pattern does not apply#

Product variations#

Your team lead brings four product changes. Each one asks what the key is.

Why this matters in real systems#

Explain it back#

In two or three sentences, explain to a teammate how you group items that belong together in one pass. Then explain why the key must be equal for every item in a group and different for every other item. The AI tutor checks your answer against the invariant and the key points of this lesson.

Here is how you could explain it in an interview, now that you have built it.

For each item, I compute a key that is the same for every item that belongs with it. For words with the same letters, the key is the letters in sorted order.

I look the key up in a map. If it is new, I start a group, and then I add the item to the group of its key.

Counting is the same move with a number in place of a list. One pass, O(n) map steps, and a record of the order the groups start.

The 60-second interview answer#

Checkpoint#

Ten questions on this lesson. Pass with 80% or more to be sure the idea has landed before the next lesson. The checkpoint of this stretch, with its two mixed problems, comes after the next lesson.

Practice ladder#

Review cards#

Five cards from this lesson join your spaced-review deck. The first one comes back tomorrow.