Grouping by key
Put items into buckets by computing a key for each one, so items that share a key end up together.
O(n * k)Space O(n)6 practice problemsStep-through pictureThe idea
Grouping means sorting items into buckets where every item in a bucket has something in common. The trick is to turn that "something in common" into a key: a value you can compute from one item alone, such that two items belong together exactly when their keys are equal.
Then a Map from key to a list does the rest. Walk the items once, compute each item's key, and push the item onto that key's list, creating the list the first time the key appears.
The hard part is choosing the key. For words that use the same letters ("tea", "eat", "ate"), the key is the word's letters sorted: "aet". For dates, the key might be the day. For files, it might be their contents.
An everyday example
Sorting the mail into cubbyholes
A mail room has a wall of cubbyholes, one per apartment. For each letter, the clerk reads the apartment number, which is the key, and drops the letter into that cubby. If a new tenant gets mail for the first time, the clerk labels a fresh cubby. At the end, each cubby holds all the mail for one apartment, and the clerk only touched each letter once.
| In the example | In the code |
|---|---|
| The wall of cubbyholes | groups, a Map from key to list |
| Reading the apartment number | key = getKey(item) |
| Labeling a fresh cubby | groups.set(key, []) |
| Dropping the letter in | groups.get(key).push(item) |
From the slow way to grouping by key
- The obvious way to group items is to compare each item with the items already grouped and ask "do these two belong together?". With
nitems that can be aboutn²comparisons, and each comparison, like checking that two words use the same letters, has its own cost. - "Belongs with" is usually a sameness rule: if
abelongs withb, andbbelongs withc, thenabelongs withc. A rule like that can be captured by a label computed from one item alone, often called its canonical form, such as a word's letters in sorted order. - If two items get equal labels exactly when they belong together, grouping no longer needs pairwise comparisons. Items with the same label go in the same group, and a hash map from label to list sorts each item into place in about constant time.
- Now the only real cost is computing each label. Walk the items once, compute the key, and push the item onto that key's list, creating the list the first time the key appears. That loop is grouping by key.
How it works
- Decide on a key function
getKeysuch that two items belong together exactly when their keys are equal. - Create an empty
Mapcalledgroups. - For each
item, computekey = getKey(item). - If
groupshas no list forkey, create an empty one. - Push
itemontogroups.get(key). - Return the lists with
[...groups.values()]. They come out in the order each key first appeared.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function groupByKey(items, getKey) {const groups = new Map();for (const item of items) {const key = getKey(item);if (!groups.has(key)) {groups.set(key, []);}groups.get(key).push(item);}return [...groups.values()];}const sortedLetters = (word) => [...word].sort().join("");groupByKey(["tea", "eat", "ant", "tan", "ate"], sortedLetters);
How fast it is
| Time | O(n * k) |
|---|---|
| Extra memory | O(n) |
Each of the n items needs its key computed, which costs k (for example, the time to sort a word's letters), plus constant-time map work. Every item is stored once.
- Best case
O(n)The key takes constant time, like grouping orders by
order.status. Each item costs a few constant steps. - Average case
O(n * k)Each key costs
ksteps. For sorted-letter keys on words of lengthm,kis aboutm log m. - Worst case
O(n * k)Long items with costly keys, such as sorting the letters of long strings. The map work stays constant per item, so the key cost decides the total.
Common mistakes
- Using an array as a
Mapkey. Two equal arrays are different keys; join them into a string first. - Building a string key without separators, so different items collide:
[1, 23]and[12, 3]both become"123". - Choosing a key that is too loose (like word length for anagrams), which merges groups that should stay apart.
- Pushing onto
groups.get(key)before creating the list, which throws becausegetreturnsundefined.
When to use it
Look for these clues in a problem:
- The problem says "group", "bucket", "cluster", or "which items are equivalent".
- Two items belong together when some property matches: same letters, same day, same shape, same content.
- The output is a list of lists.
- A brute force would compare every pair of items to see if they belong together.
Check yourself
Answer each one in your head first, then open it.
What key does "lemon" get, and which word in the trace shares it?
"elmno", the same as "melon". Both use the letters e, l, m, n, o once each.
What goes wrong if the code calls groups.set(key, []) for every item, not just new keys?
Each call replaces the list with an empty one, throwing away earlier items. Every group would end up with only its last item.
In what order do the groups come out?
In the order their keys were first added to the Map, which is the order of each group's first item in the input.
How long does grouping n words of length m take with sorted-letter keys?
O(n * m log m): each word's letters are sorted once, and the map work per word is constant.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingmedium
Go further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
Everything rests on one property of the key: getKey(a) === getKey(b) exactly when a and b belong together. For words made of the same letters, this holds because two words use the same letters the same number of times exactly when their sorted letters form the same string.
The loop keeps a rule: after some items are handled, each list in groups holds, in input order, exactly the handled items with that list's key, and every handled item is in exactly one list. Pushing the next item onto its key's list, after creating the list if needed, keeps the rule true.
The loop ends after the last item. Then every item is in exactly one list, and by the key property each list is one whole group. groups.values() returns the lists in the order their keys were first added, which is why the first group holds the first item.
Going deeper
3 more ideas
Why a good key is everything
Grouping by key is only correct if the key is the same for items that belong together and different for items that don't. Sorting a word's letters works for anagrams because two words use the same letters exactly when their sorted letters are the same string. A weaker key, like the word's length, would put "tea" and "dog" together.
Keys must be strings or numbers
A Map compares array keys by identity, so [1, 2] and another [1, 2] would be different keys. When a key has several parts, join them into a string, such as counts.join(",") or row + ":" + col. Keep a separator so [1, 23] and [12, 3] don't both become "123".
Cost
Each item costs one key computation plus constant-time map work. If computing a key takes O(k) time (sorting a word of length k takes O(k log k)), the total is n times that. The map and lists hold every item once: O(n) space. Modern JavaScript also has Map.groupBy(items, getKey), which does exactly this.
Work it by hand
Every step in a table, with why
Group six words by their sorted letters, so words made of the same letters end up together.
items = ["sale", "melon", "leas", "lemon", "ales", "kiwi"], getKey = sortedLetters
| Step | item | key | New key? | That group now | Groups | Why |
|---|---|---|---|---|---|---|
| 1 | "sale" | "aels" | yes | [sale] | 1 | Sorting the letters s, a, l, e gives "aels". No group has that key, so groups.set("aels", []) makes one. |
| 2 | "melon" | "elmno" | yes | [melon] | 2 | A different key, so a second group starts. |
| 3 | "leas" | "aels" | no | [sale, leas] | 2 | Same letters as sale, so the same key. The word joins that group without being compared to sale directly. |
| 4 | "lemon" | "elmno" | no | [melon, lemon] | 2 | lemon and melon share the key "elmno". |
| 5 | "ales" | "aels" | no | [sale, leas, ales] | 2 | A third word joins the first group. Inside a group, words stay in input order. |
| 6 | "kiwi" | "iikw" | yes | [kiwi] | 3 | Repeated letters stay in the key: two is give "iikw". A new group starts. |
It returns [["sale", "leas", "ales"], ["melon", "lemon"], ["kiwi"]]. The groups come out in the order their keys first appeared, and each word was handled once.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Grouping by key | O(n * k) | O(n) | An exact key exists that two items share exactly when they belong together. |
| Sort by key, then cut into runs | O(n log n) | O(n) | You also want the groups in sorted key order, such as alphabetical sections. |
| Compare each item with each group | O(n²) | O(n) | There's no exact key, only a pairwise test like "these two prices are within 5%". |
Extra memory: O(n) for the lists, which hold every item once, plus the keys. String keys of length m can add up to O(n * m) characters when every key is different.
How the steps grow
- Grouping by key, Compare each item with each group
O(n * k) - Sort by key, then cut into runs
O(n log n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Grouping by key | 100 | 1 million | 1 trillion |
| Sort by key, then cut into runs | 33 | 9,966 | 20 million |
| Compare each item with each group | 100 | 1 million | 1 trillion |
Inputs that need care
5 tricky inputs
- An empty list:
items = [] - The loop never runs and the result is
[]. - Every item has the same key
- One list holds all items, in input order, and the result is
[items]. - Every key is different
- The result is
nlists of one item each, and the map hasnkeys. - Letters in different case:
["Lemon", "melon"] - Sorted, these are
"Lemno"and"elmno", so they land in different groups. Lowercase the word insidegetKeyif case shouldn't matter. - Items with no key, like objects missing the grouped field
getKeyreturnsundefined, and aMapacceptsundefinedas a key, so all of them form one group. Decide whether to keep that group or skip those items.
Variations and follow-ups
Twists interviewers add
A key without sorting
For lowercase words, count each letter into an array of 26 numbers and join it with a separator, like "1#0#0#...". That costs O(m) per word instead of O(m log m), which helps when words are long.
Group, then total
Instead of a list per key, keep a running number per key: total spent per customer, or errors per page. It's the same loop with groups.set(key, (groups.get(key) ?? 0) + amount) in place of push.
Sections sorted by key
For a contacts list grouped by first letter, group first, then sort the keys and read the groups in that order. Sorting only the keys is cheaper than sorting all the items.
Shape keys
Some groups share a pattern instead of letters. Strings that are shifts of each other, like "ace" and "bdf", share the gaps between neighboring letters, so a key like "2,2" groups them.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from words like "group", "bucket", "categorize", "same letters", or "same pattern". The task is to sort items into piles, not to order them.
- Say the key idea first: "I'll compute a key so that two items share a key exactly when they belong together." Then argue that property for your key.
- Test by hand: an item that appears twice, an item alone in its group, and two items that look alike but differ in a small way, like case or a repeated letter.
- The usual follow-up is "can the key be cheaper than sorting the letters?". Answer: count the letters into 26 slots and join the counts with a separator, which is
O(m)per word.
Where frontend code uses it
The same idea in real UI code
- Grouping notifications or chat messages by day to draw "Today", "Yesterday", and date headers.
- Grouping search results or products by category for a sectioned list.
Object.groupByandMap.groupBy, added to JavaScript in 2024, do this grouping for you in modern browsers.- Bundlers group modules by the chunk they belong to when splitting code into files.