Skip to main content

16. Group Anagrams

mediumAsked at Monzo

Group merchant descriptor variants that share the same letters so they map to one category.

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

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

Example 2

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

Approaches

1. Sort each string as key

Sort the characters of each string and use the sorted form as a hash map key.

Time
O(n * k log k)
Space
O(n*k)
const m = new Map();
for (const s of strs) {
  const k = [...s].sort().join('');
  if (!m.has(k)) m.set(k, []);
  m.get(k).push(s);
}
return [...m.values()];

Tradeoff:

2. Letter-count signature

Build a 26-slot count array per string and use its string form as the bucket key. Avoids sorting.

Time
O(n*k)
Space
O(n*k)
function groupAnagrams(strs) {
  const m = new Map();
  for (const s of strs) {
    const c = new Array(26).fill(0);
    for (const ch of s) c[ch.charCodeAt(0) - 97]++;
    const k = c.join('#');
    if (!m.has(k)) m.set(k, []);
    m.get(k).push(s);
  }
  return [...m.values()];
}

Tradeoff:

Monzo-specific tips

Monzo grades for the leap from sort-as-key to count-signature; that move maps directly to how they de-duplicate merchant names in the ledger.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →