Skip to main content

18. Group Anagrams

mediumAsked at SoFi

Group strings that are anagrams of each other — SoFi uses this to see if you can pick the right canonical key, a common move in transaction-categorization pipelines.

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.

Constraints

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters

Examples

Example 1

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

Example 2

Input
[""]
Output
[[""]]

Approaches

1. Brute force pairs

For each string, compare against every existing group's first member by sorting both.

Time
O(n^2 * k log k)
Space
O(n*k)
function groupAnagrams(strs) {
  const groups = [];
  const sorted = s => [...s].sort().join('');
  for (const s of strs) {
    const g = groups.find(g => sorted(g[0]) === sorted(s));
    if (g) g.push(s); else groups.push([s]);
  }
  return groups;
}

Tradeoff:

2. Hash map with sorted-string key

Use the sorted form of each string as a canonical key in a hash map; values are the grouped lists.

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

Tradeoff:

SoFi-specific tips

SoFi favors candidates who think about the canonical-key trick — it's the same pattern used to bucket merchant categorization codes (MCCs) for spend reports across millions of card transactions.

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 SoFi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →