Frequency counting

33 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Someone hands you six words: eat, tea, tan, ate, nat, bat, and asks you to group the ones that are anagrams, meaning they use exactly the same letters. By hand you would compare word pairs: is "eat" an anagram of "tea"? Check that each has one e, one a, one t. Yes. Is "eat" an anagram of "tan"? No. You keep going until every pair has been compared.

Six words make 15 pairs, and each comparison means counting letters in both words. For n words that is about n² ÷ 2 pair checks. A hundred thousand words would need about five billion checks. The waste is obvious once you see it: you keep re-counting the letters of the same word for every partner it is compared with.

Build the structure, one piece at a time

The fix has two parts, and both are about counting once.

First, decide what "the same letters" really means. Two words are anagrams exactly when their letter counts match: the same number of a's, the same number of b's, and so on. So the identity of a word, for this question, is its count table. Write that table in a fixed way, for example by sorting the letters: eat → aet, tea → aet, tan → ant. Now equal words have equal signatures and you can check equality by comparing two short strings.

Second, use a hash map whose keys are signatures and whose values are lists of words. A hash map finds a key in about one step however many keys it holds. Walk the words once, compute each signature, and append the word to that key's list:

The lists in the map are the answer. The same machine answers many other questions. Count how often each value appears and the map becomes a counter: the key is the value, the entry is how many times it was seen. "Which element appears more than half the time", "which character appears only once", "which k elements are most frequent" are all one pass to build the counter, then one question asked of it.

Why it is correct

The invariant is simple: after processing the first i items, the counter is exact for those i items. Each step updates exactly one entry by exactly one, so if the counts were right before the step they are right after it.

For grouping, correctness rests on the signature being a true fingerprint: two words get the same signature if and only if they have the same letter counts. Sorting letters gives that, because a sorted string is determined by the counts and determines them. So every anagram lands in the same bucket and no non-anagram does.

Why it is fast

Building the counter is one update per item, about one step each, so O(n). Grouping anagrams costs one signature per word; sorting a word of k letters is O(k log k), or O(k) if you build a 26-entry count table instead, so the total is about O(n · k). Each word's letters are counted once, not once per partner. For a hundred thousand words of five letters that is roughly half a million letter operations instead of five billion pair checks. Memory is one entry per distinct key, O(k) for k distinct keys.

How to recognise it in an interview

Cues: "anagram", "appears more than", "most frequent", "first unique", "can string A be built from the letters of B". Whenever the answer depends only on how many of each thing there is and not on where they are, count first.

Say: "I will count in one pass with a hash map, then answer from the counts." Valid Anagram is two counters compared. Majority Element is a counter followed by "which key has count greater than n/2". Top K Frequent Elements is a counter followed by picking the k largest counts, usually with a heap or bucket sort.

02The idea in one line

Count first; the answer is a question about the counts.

Reach for it when: Anagrams, majority, 'first unique', top-k, 'can be formed from'.

Cost: O(n) time, O(k) space for k distinct keys.

03The walk-through, step by step

The video works one example: Group Anagrams by sorted-key signature. These are its captions in order, so you can follow without the video or check a step you missed.

1. Equal letter counts ⇔ equal sorted key; bucket by the key
2. 'eat' sorts to 'aet': new bucket
3. 'tea' sorts to 'aet': join its bucket
4. 'tan' sorts to 'ant': new bucket
5. 'ate' sorts to 'aet': join its bucket
6. 'nat' sorts to 'ant': join its bucket
7. 'bat' sorts to 'abt': new bucket
8. Three buckets: [eat tea ate] [tan nat] [bat]
9. Sorting each word costs k log k: O(n · k log k); counting letters makes it O(n·k)

04Asked at Google

13 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Arrays & Hashing: Hash the complement, Canonical key hashing, In-place index hashing, Set-start expansion, Seen-set cycle detection.