49. Group Anagrams

Q: Why is the sorted-string approach O(k log k) and not O(k²)?

Sorting a string of length k uses a comparison sort (e.g., timsort) at O(k log k). The join is O(k). Total per string: O(k log k).

Q: Can I use a number-based hash instead of a string key?

Yes — prime-product hashing (assign each letter a unique prime, multiply) gives a unique key. But it risks integer overflow for long strings and is harder to explain under interview pressure. String keys are cleaner.

Q: Does the output order matter?

The problem says 'any order,' so no. Your Map iteration order is insertion order in JavaScript, which is fine.

mediumAsked at eBay

eBay's catalog deduplication system groups semantically equivalent product titles — 'Nike Shoe Air Max' and 'Air Max Nike Shoe' should map to the same listing cluster. Group Anagrams is the algorithmic skeleton: given a set of strings, bucket them by canonical form. Choosing the right canonical key (sorted vs. frequency count) reveals your understanding of hashing and time-space tradeoffs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in eBay loops.

Glassdoor (2025-12)— Reported as a common eBay medium problem focused on hashing and string canonicalization.
Blind (2025-10)— eBay SWE threads list Group Anagrams as a representative problem for the string/hashing section of their interview loop.

Problem

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word or phrase formed by rearranging the letters of another.

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"]]

Explanation: The three anagram groups are {bat}, {tan, nat}, and {eat, tea, ate}.

Example 2

Input

strs = [""]

Output

[[""]]

Explanation: Single empty string — one group.

Example 3

Input

strs = ["a"]

Output

[["a"]]

Explanation: Single character — one group.

Approaches

1. Sort each string as key

For each string, sort its characters to produce a canonical key. Use a Map from sorted-string to list of originals.

Time: O(n · k log k) where k is max string length
Space: O(n · k)

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 Array.from(map.values());
}

Tradeoff: Simple and correct. O(k log k) per string for sorting. The canonical answer most eBay interviewers accept — clean code, easy to reason about.

2. Character frequency count as key

Build a 26-element frequency array for each string. Serialize it as a string key (e.g., '#1#0#0...') to avoid collisions. Avoids sorting.

Time: O(n · k)
Space: O(n · k)

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

Tradeoff: O(n · k) — better when strings are long. The separator '#' prevents hash collisions between frequency arrays (e.g., [1,10,...] vs [11,0,...] would stringify identically without a separator).

eBay-specific tips

eBay interviewers often ask: 'What if the strings can be very long?' That's the cue to introduce the frequency-count approach. Always explain why you need a separator in the key: 'a#1' could collide with 'a1' if you omit the delimiter. Mention that both approaches are O(nk) in space since you store all strings; the time difference is the sorting constant. For the standard constraint (k ≤ 100), both are perfectly fine.

Common mistakes

Using count.join('') without a separator — creates hash collisions between distinct frequency profiles (e.g., [1,11] and [11,1] both become '111').
Modifying the input strings in place while sorting — always work on a copy (split/sort/join).
Returning map.keys() instead of map.values() — keys are the canonical strings, not the grouped originals.
Forgetting to handle empty strings — they sort to '' and frequency-count to all zeros; both keys are valid and consistent.

Follow-up questions

An interviewer at eBay may pivot to one of these next:

Valid Anagram (LC 242) — check if two specific strings are anagrams; simpler base case.
Find All Anagrams in a String (LC 438) — sliding-window frequency comparison.
How would you scale this to a distributed system where strings arrive in a stream too large for a single machine?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the sorted-string approach O(k log k) and not O(k²)?

Sorting a string of length k uses a comparison sort (e.g., timsort) at O(k log k). The join is O(k). Total per string: O(k log k).

Can I use a number-based hash instead of a string key?

Yes — prime-product hashing (assign each letter a unique prime, multiply) gives a unique key. But it risks integer overflow for long strings and is harder to explain under interview pressure. String keys are cleaner.

Does the output order matter?

The problem says 'any order,' so no. Your Map iteration order is insertion order in JavaScript, which is fine.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →