Skip to main content

49. Group Anagrams

mediumAsked at Shopify

Group 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 Alex Chen, 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^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Examples

Example 1

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

Example 2

Input
strs = [""]
Output
[[""]]

Example 3

Input
strs = ["a"]
Output
[["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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Group Anagrams and other Shopify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →