Skip to main content

47. Group Anagrams

mediumAsked at Datadog

Group strings that are anagrams of each other. Datadog asks this because the canonicalize-then-hash pattern is identical to how they group equivalent metric series by sorted-tag-keys for query deduplication.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — direct analog to tag-set canonicalization.
  • Blind (2025-11)— Recurring Datadog problem.

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 a different word or phrase, typically using all the 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
[[""]]

Approaches

1. Compare every pair

For each string, scan all groups; check if it's an anagram of the group's representative.

Time
O(n^2 * k log k)
Space
O(n * k)
// Compare each new string against every group's representative; O(n^2).

Tradeoff: Quadratic — fails on 10^4 inputs. Datadog will reject.

2. Sorted-key hashmap (optimal)

Sort each string's chars to get its canonical key. Group by key in a Map.

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 [...groups.values()];
}

Tradeoff: Canonical pattern. Datadog uses the same canonicalize-then-hash for grouping equivalent tag-sets across millions of metrics.

Datadog-specific tips

Datadog will follow up with: 'What if k (string length) is large?' The answer: use a count-of-26-letters tuple as the key instead of a sorted string. O(n * k) instead of O(n * k log k). Articulate both keys before they ask.

Common mistakes

  • Using JSON.stringify on a count array — slower than a direct string concatenation key.
  • Mutating the input by sorting strs in place — touches the wrong object.
  • Forgetting that JS sort on chars is lexical but defined — works for lowercase, breaks if Unicode is involved.

Follow-up questions

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

  • Valid Anagram (LC 242) — single-pair version.
  • Datadog-style: group metric series by tag-set (sort tag keys for canonical form).
  • Group Shifted Strings (LC 249) — different canonical key.

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 does sorting work as a canonical key?

Two strings are anagrams iff their sorted forms are equal. Sorting maps the equivalence class to a unique representative.

When is count-of-26 better than sort?

When k > 26 (so sort cost k log k > 26). At Datadog scale where tag values can be long, the count-array key wins.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →