Part 5 · Lesson 27 · 24 min read
Frequency Maps and Grouping
Anagrams, top frequencies, the majority element and grouping by a key.
On this page
Group things that share a key
Lesson 26 used a Map to remember single values. This lesson uses a Map to collect values. A Map is a collection of key → value pairs. Every item is turned into a key (a label). Items with the same key go into the same list or the same count. Think of sorting post into one box for each street name. The hard part of these problems is choosing the key.
Designing a good key
A good key is equal for two items exactly when they belong together. An anagram is a word made from the same letters as another word in a different order, such as “listen” and “silent”. For anagrams there are two common keys:
// Key 1: the letters sorted — O(L log L) per wordconst sortedKey = (w) => [...w].sort().join("");// Key 2: the 26 letter counts joined — O(L) per wordfunction countKey(w) { const c = new Array(26).fill(0); for (const ch of w) c[ch.charCodeAt(0) - 97]++; return c.join(",");}console.log(sortedKey("listen"), sortedKey("silent")); // eilnst eilnstconsole.log(countKey("abca") === countKey("caba")); // trueBoth keys are strings (text). This matters in JavaScript. A Map compares arrays by identity (is it the very same array object?), not by contents (Lesson 15). So an array of counts cannot be the key directly. Join it into text first.
Use join(","), not join(""). Without a separator, the counts [1, 11] and [11, 1] would both become “111”. Two different keys would turn into the same key. This is called a collision.
Group anagrams
The task: given a list of words, put the anagrams together. Work out each word's key and add the word to the list for that key. This takes one pass, and you never compare two words with each other.
Traced: grouping six words
A Map from each key to the list of words with that key.
1const words = ["eat", "tea", "tan", "ate", "nat", "bat"];▶const groups = new Map();3for (const w of words) {4 const key = [...w].sort().join("");5 if (!groups.has(key)) groups.set(key, []);6 groups.get(key).push(w);7}8console.log([...groups.values()]);| groups | Map(0) {} |
Say there are n words, each up to L letters long. The sorted key takes O(n · L log L) time. The count key takes O(n · L) time. Comparing every pair of words instead would take O(n² · L) time.
Grouping by anything
The same few lines can group by any key: length, first letter, remainder, or a field of an object. The function keyOf tells the code which key to use for each item:
function groupBy(items, keyOf) { const groups = new Map(); for (const item of items) { const k = keyOf(item); if (!groups.has(k)) groups.set(k, []); groups.get(k).push(item); } return groups;}console.log(groupBy(["apple", "kiwi", "fig", "plum"], (w) => w.length));// Map(3) { 5 => [ 'apple' ], 4 => [ 'kiwi', 'plum' ], 3 => [ 'fig' ] }// Newer JavaScript (ES2024, Node 21 and later) has this built in:console.log(Map.groupBy([1, 2, 3, 4, 5], (n) => (n % 2 === 0 ? "even" : "odd")));// Map(2) { 'odd' => [ 1, 3, 5 ], 'even' => [ 2, 4 ] }Top k frequent: sort or buckets
The task: find the k values that appear most often. First count each value with a Map. Then put the values in order by count. Sorting the entries takes O(n log n) time. The bucket idea from Lesson 15 avoids sorting. A bucket is a list that holds all values with the same count. A count can never be bigger than n, so use the count as an array index. Then read the buckets from the highest count down.
function topKFrequent(nums, k) { const freq = new Map(); for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1); // bucket[c] = values that appear exactly c times (c is at most n) const bucket = Array.from({ length: nums.length + 1 }, () => []); for (const [x, c] of freq) bucket[c].push(x); const out = []; for (let c = nums.length; c >= 1 && out.length < k; c--) { for (const x of bucket[c]) { if (out.length < k) out.push(x); } } return out;}console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [ 1, 2 ]| Step | Result |
|---|---|
| counts | 1 → 3, 2 → 2, 3 → 1 |
| buckets | bucket[3] = [1], bucket[2] = [2], bucket[1] = [3] |
| read from c = 6 down | take 1 (c = 3), then 2 (c = 2) — done |
O(n) time. A heap (a structure that always gives you the biggest item quickly) gives O(n log k), which Lesson 46 covers.
Majority element and Boyer–Moore voting
The majority element is the value that appears more than n/2 times (n is the length of the array). A frequency map finds it in O(n) time and O(n) space. Sorting and taking the middle value also works, because the majority value must cover the middle position. There is also a method that needs only O(1) extra space: Boyer–Moore voting.
Imagine each value is a vote. Keep a current candidate and a vote count. A value that matches the candidate adds one vote. A different value cancels one vote. When the count drops to 0, the next value becomes the candidate. The majority value has more votes than all the other values together. So the others cannot cancel it completely, and it is the candidate at the end.
function majorityElement(nums) { let candidate = null, votes = 0; for (const x of nums) { if (votes === 0) candidate = x; // no current leader: x becomes the candidate votes += x === candidate ? 1 : -1; // a matching vote adds one, a different value cancels one } return candidate;}console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2| x | candidate | votes |
|---|---|---|
| 2 | 2 | 1 |
| 2 | 2 | 2 |
| 1 | 2 | 1 |
| 1 | 2 | 0 |
| 1 | 1 | 1 |
| 2 | 1 | 0 |
| 2 | 2 | 1 |
If the problem does not promise that a majority exists, the final candidate might be wrong. Then do a second pass to count the candidate and confirm it.
Isomorphic strings: a two-way mapping
Two strings are isomorphic if you can change the letters of one string to get the other. Each letter must always change to the same letter, and no two different letters may change to the same letter. One Map is not enough. It catches “o → a and o → r” but not “b → b and d → b”. So use one Map for each direction:
function isIsomorphic(s, t) { const st = new Map(), ts = new Map(); for (let i = 0; i < s.length; i++) { const a = s[i], b = t[i]; if ((st.has(a) && st.get(a) !== b) || (ts.has(b) && ts.get(b) !== a)) return false; st.set(a, b); ts.set(b, a); } return true;}console.log(isIsomorphic("egg", "add")); // true e→a, g→dconsole.log(isIsomorphic("foo", "bar")); // false o would need to map to both a and rconsole.log(isIsomorphic("badc", "baba")); // false b and d would both map to bThe same two-Map check solves “word pattern” (Practice question 6), where letters map to whole words.
Practice questions
For each grouping question, write the key function first. Test it on two items that should match and two items that should not.
Return true if every value in arr appears a different number of times.
Hint 1
Show the solution with explanations
A Set keeps only unique values. If no two counts are equal, the Set of counts has the same size as the Map.
function uniqueOccurrences(arr) { const freq = new Map(); for (const x of arr) freq.set(x, (freq.get(x) ?? 0) + 1); return new Set(freq.values()).size === freq.size;}console.log(uniqueOccurrences([1, 2, 2, 1, 1, 3])); // trueconsole.log(uniqueOccurrences([1, 2])); // falseO(n) time. Comparing the two sizes is a common way to ask “are they all different?”.
(LeetCode 1207.)
Group the words that are anagrams of each other.
Hint 1
Show all 2 solutions with explanations
Group words by their sorted letters.
function groupAnagrams(strs) { const groups = new Map(); for (const w of strs) { const key = [...w].sort().join(""); if (!groups.has(key)) groups.set(key, []); groups.get(key).push(w); } return [...groups.values()];}console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));// [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]O(n · L log L) for n words of length L.
Group by the 26 counts joined into a string.
function groupAnagrams(strs) { const groups = new Map(); for (const w of strs) { const c = new Array(26).fill(0); for (const ch of w) c[ch.charCodeAt(0) - 97]++; const key = c.join(","); if (!groups.has(key)) groups.set(key, []); groups.get(key).push(w); } return [...groups.values()];}console.log(groupAnagrams([""])); // [ [ '' ] ]O(n · L) time. This is slightly better for long words. Sorted keys are fine in most interviews.
This is one of the most common interview questions. Explain your key choice and its cost. (LeetCode 49.)
Return the k most frequent values, in any order.
Hint 1
Hint 2
Show all 2 solutions with explanations
Sort the Map entries by count, descending, and take the first k values.
function topKFrequent(nums, k) { const freq = new Map(); for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1); return [...freq].sort((a, b) => b[1] - a[1]).slice(0, k).map(([x]) => x);}console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [ 1, 2 ]O(n log n) time in the worst case (when all values are different).
The method from the lesson.
function topKFrequent(nums, k) { const freq = new Map(); for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1); const bucket = Array.from({ length: nums.length + 1 }, () => []); for (const [x, c] of freq) bucket[c].push(x); const out = []; for (let c = nums.length; c > 0 && out.length < k; c--) out.push(...bucket[c]); return out.slice(0, k);}console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [ 1, 2 ]console.log(topKFrequent([1], 1)); // [ 1 ]O(n) time and O(n) space.
The problem asks for better than O(n log n). Use buckets (O(n)) or a heap (O(n log k), Lesson 46). (LeetCode 347.)
Return the value that appears more than n / 2 times. It always exists.
Hint 1
Show all 3 solutions with explanations
Return the first value whose count passes n / 2.
function majorityElement(nums) { const freq = new Map(); for (const x of nums) { freq.set(x, (freq.get(x) ?? 0) + 1); if (freq.get(x) > nums.length / 2) return x; }}console.log(majorityElement([3, 2, 3])); // 3O(n) time, O(n) space.
A value that fills more than half of the sorted array must be at the middle index.
function majorityElement(nums) { const a = [...nums].sort((x, y) => x - y); return a[Math.floor(a.length / 2)];}console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2O(n log n) time. The code is very short.
The method from the lesson.
function majorityElement(nums) { let candidate = null, votes = 0; for (const x of nums) { if (votes === 0) candidate = x; votes += x === candidate ? 1 : -1; } return candidate;}console.log(majorityElement([3, 2, 3])); // 3console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2O(n) time, O(1) space.
Show all three, from simplest to best. A strong answer sounds like this. (LeetCode 169.)
Return every value that appears more than ⌊n / 3⌋ times.
Hint 1
Hint 2
Show all 2 solutions with explanations
Count the values, then keep those with a high count.
function majorityElement(nums) { const freq = new Map(); for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1); return [...freq].filter(([, c]) => c > nums.length / 3).map(([x]) => x);}console.log(majorityElement([1, 1, 1, 3, 3, 2, 2, 2])); // [ 1, 2 ]O(n) time, O(n) space.
This is Boyer–Moore voting with two candidates. A check follows, because a candidate may not really appear more than n/3 times.
function majorityElement(nums) { let c1 = null, c2 = null, v1 = 0, v2 = 0; for (const x of nums) { if (x === c1) v1++; else if (x === c2) v2++; else if (v1 === 0) { c1 = x; v1 = 1; } else if (v2 === 0) { c2 = x; v2 = 1; } else { v1--; v2--; } } return [c1, c2].filter( (c, i, arr) => c !== null && arr.indexOf(c) === i && nums.filter((x) => x === c).length > nums.length / 3, );}console.log(majorityElement([3, 2, 3])); // [ 3 ]console.log(majorityElement([1, 2])); // [ 1, 2 ]console.log(majorityElement([1, 1, 1, 3, 3, 2, 2, 2])); // [ 1, 2 ]O(n) time, O(1) extra space. The verification pass is required here, unlike Question 4.
This is a good follow-up. It shows that you understand why voting works, not just the code. (LeetCode 229.)
Return whether the words of s follow pattern: each letter matches one word, and each word matches one letter.
Hint 1
Show the solution with explanations
The map from letter to word and the map from word to letter must both stay consistent.
function wordPattern(pattern, s) { const words = s.split(" "); if (words.length !== pattern.length) return false; const pw = new Map(), wp = new Map(); for (let i = 0; i < words.length; i++) { const p = pattern[i], w = words[i]; if ((pw.has(p) && pw.get(p) !== w) || (wp.has(w) && wp.get(w) !== p)) return false; pw.set(p, w); wp.set(w, p); } return true;}console.log(wordPattern("abba", "dog cat cat dog")); // trueconsole.log(wordPattern("abba", "dog dog dog dog")); // falseconsole.log(wordPattern("aaa", "dog dog")); // falseO(n) time. The length check stops the loop from reading past the end of either list.
(LeetCode 290.)
Return whether s can be turned into t by always replacing a character with the same character. No two different characters may map to the same character.
Hint 1
Hint 2
Show all 2 solutions with explanations
The method from the lesson.
function isIsomorphic(s, t) { const st = new Map(), ts = new Map(); for (let i = 0; i < s.length; i++) { if ((st.get(s[i]) ?? t[i]) !== t[i] || (ts.get(t[i]) ?? s[i]) !== s[i]) return false; st.set(s[i], t[i]); ts.set(t[i], s[i]); } return true;}console.log(isIsomorphic("paper", "title")); // trueconsole.log(isIsomorphic("badc", "baba")); // falseO(n) time. ?? t[i] means “if this letter has no mapping yet, any letter is fine”.
Replace each character by the index where it first appears. Isomorphic strings give the same pattern.
function isIsomorphic(s, t) { const pattern = (str) => [...str].map((ch) => str.indexOf(ch)).join(","); return pattern(s) === pattern(t);}console.log(isIsomorphic("paper", "title")); // trueconsole.log(isIsomorphic("badc", "baba")); // false| String | First-occurrence pattern |
|---|---|
| paper | 0,1,0,3,4 |
| title | 0,1,0,3,4 |
| badc | 0,1,2,3 |
| baba | 0,1,0,1 |
indexOf is a hidden loop, so this is O(n²) for long strings. But it is a nice key idea: the pattern is a key that is equal exactly for isomorphic strings.
Use the two Maps in interviews. Remember the pattern idea for grouping questions such as “group isomorphic words”. (LeetCode 205.)
Make it stick
- Write two different anagram keys and say the cost of each.
- Explain the bucket method for top k frequent and why it is O(n).
- Dry-run Boyer–Moore voting on [3, 3, 4, 2, 3].
- Explain why isomorphic strings need two Maps.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
Part 5 complete — what's next
You can now use Maps and Sets to remember, count and group. These tools solve many medium-level interview questions.
Part 6 — Binary Search shows a very different way to be fast. On sorted data, you throw away half of the remaining possibilities with every comparison. This takes O(log n) time.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series