49. Group Anagrams
mediumAsked at ShopifyGroup Anagrams shows up at Shopify because product-search ranking and tag-deduplication both reduce to 'bucket by canonical key'. The interviewer is grading whether you pick the right hash key (sorted string vs char-count tuple) and explain the time tradeoff.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Shopify loops.
- Glassdoor (2026-Q1)— Shopify Backend Developer + Production Engineer phone screens list Group Anagrams as a medium round.
- Reddit r/cscareerquestions (2025-10)— Multiple Shopify new-grad reports include Group Anagrams with a follow-up about scaling to large k (word length).
Problem
Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word formed by rearranging the letters of another, using all original letters exactly once.
Constraints
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i] consists of lowercase English letters.
Examples
Example 1
strs = ["eat","tea","tan","ate","nat","bat"][["bat"],["nat","tan"],["ate","eat","tea"]]Example 2
strs = [""][[""]]Example 3
strs = ["a"][["a"]]Approaches
1. Brute-force pairwise comparison
For each string, scan the result groups; insert into a group whose head is an anagram (by sorted-string equality), else start a new group.
- Time
- O(n^2 * k log k)
- Space
- O(n * k)
function groupAnagramsBrute(strs) {
const groups = [];
for (const s of strs) {
const sorted = s.split('').sort().join('');
let placed = false;
for (const g of groups) {
if (g.sorted === sorted) {
g.items.push(s);
placed = true;
break;
}
}
if (!placed) groups.push({ sorted, items: [s] });
}
return groups.map(g => g.items);
}Tradeoff: Quadratic in n — every input is compared against every existing group. Don't ship this; use it only to motivate the hash-map version.
2. Hash map keyed by sorted string (optimal)
For each input, sort its characters to produce a canonical key, then bucket into a Map. Return Array.from(map.values()).
- Time
- O(n * k log k)
- Space
- O(n * k)
function groupAnagrams(strs) {
const groups = new Map();
for (const s of strs) {
const key = s.split('').sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(s);
}
return Array.from(groups.values());
}Tradeoff: Linear in n with a k log k factor per string for the sort. n = 10^4, k = 100 means ~10^4 * 100 * 7 = 7M ops — comfortably under a second.
3. Hash map keyed by char-count tuple (best asymptotic)
Skip the sort; encode each string as a 26-length char-count vector and use that as the key. Drops the log factor.
- Time
- O(n * k)
- Space
- O(n * k)
function groupAnagramsCount(strs) {
const groups = new Map();
for (const s of strs) {
const counts = new Array(26).fill(0);
for (const ch of s) counts[ch.charCodeAt(0) - 97]++;
const key = counts.join(',');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(s);
}
return Array.from(groups.values());
}Tradeoff: Strictly better asymptotic, but in practice the sort-key version is shorter and often faster on the LeetCode test suite due to V8's optimized sort. Shopify interviewers will accept either if you explain the tradeoff.
Shopify-specific tips
Shopify's follow-up is usually 'what if the strings are very long (10^6 chars) but there are only 10^3 of them' — that's when the count-vector version wins clearly. They also probe alternate encodings: 'what if we have Unicode, not just a-z?' (Map<char, count> or prime-product hash). Volunteer the count-vector approach AFTER the sorted-key one so the interviewer sees both.
Common mistakes
- Using the string itself as the key (only matches identical strings, not anagrams).
- Forgetting that the empty string is a valid anagram group.
- Joining the count vector without a separator — counts[1] = 11 and counts[2] = 1 then both produce '111'. Always use a delimiter.
- Sorting in place with .sort() on the original array — corrupts subsequent comparisons.
Follow-up questions
An interviewer at Shopify may pivot to one of these next:
- What if the strings can contain Unicode characters? (Map<codepoint, count> instead of length-26 vector.)
- Stream version: input arrives one string at a time, return current groups.
- Find anagrams that differ by exactly one character.
- What if k is huge (10^6) but n is small (100)? (Count vector wins decisively.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Is the sort-key version actually slower than the count-vector version?
Asymptotically yes (O(k log k) vs O(k) per string), but in practice the JS engine's native sort is so fast that for k <= 100 the sort version often wins on LeetCode's test data. The count-vector version becomes strictly better around k >= 1000.
Why not use a prime-product hash?
Assign each letter a prime (a=2, b=3, c=5, ...). The product is the key. It works for small alphabets but overflows for k > ~15 unless you use BigInt. Cute, but not what Shopify expects on the whiteboard.
Free learning resources
Curated free links for this problem.