Group anagrams — sort key vs count key

The problem

LeetCode 49 — Group Anagrams. Given an array of strings, group the anagrams together.

Input:  ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

“eat”, “tea”, and “ate” are anagrams — same letters, different order. “tan” and “nat” are another group. “bat” is alone.

The core question: how do you know two strings are anagrams without comparing every pair?

If you compare every pair, that’s O(n² × k log k). Too slow. You need a key: a transformation where all anagrams produce the same output. Then you group by that key in O(n).

Approach 1: sort key — O(n × k log k)

Sort each string’s characters. All anagrams produce the same sorted string. Use it as a hash map key.

"eat" → sorted → "aet". "tea" → sorted → "aet". Same key → same group.

function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

Simple and clean. Sort costs O(k log k) per string, so total time is O(n × k log k).

Approach 2: count key — O(n × k)

Instead of sorting, count character frequencies. Build a key from the counts.

function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const count = new Array(26).fill(0);
    for (const c of s) count[c.charCodeAt(0) - 97]++;
    const key = count.join('#');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

No sort. Counting is O(k) per string. Total time: O(n × k).

The benchmark

Input	Sort Key	Count Key	Winner
30 words, len=5	0.026ms	0.054ms	Sort 2.1× faster
250 words, len=8	0.237ms	0.268ms	Sort 1.1× faster
500 words, len=10	0.683ms	0.534ms	Count 1.3× faster
2,000 words, len=15	3.502ms	2.638ms	Count 1.3× faster
5,000 words, len=20	11.552ms	6.878ms	Count 1.7× faster

The surprise: at n=30, sort is 2.1× FASTER than count — even though count has better Big O. JavaScript’s sort() (TimSort) is highly optimized, while building a 26-element array and joining it has constant-factor overhead that dominates on tiny inputs.

The crossover happens around n=250-500. Above that, count’s O(k) per string beats sort’s O(k log k), and the gap grows.

The hash pattern — Day 12 extends it

Day	Problem	Question	Structure
4	Contains Duplicate	”Seen this?”	Hash set
5	Valid Anagram	”How many?”	Hash map (count)
11	Two Sum	”What do I need?”	Hash map (lookup)
12	Group Anagrams	”Who’s like me?”	Hash map (grouping)

The pattern: hash maps answer questions in O(1). The question determines the key. Grouping → canonical form as key, list as value.

Check your understanding