Group AnagramsMedium

Given an array of strings, group the anagrams together. The order of the groups, and the order within a group, doesn't matter.

Examples

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

Approach

Brute force compares every string against every existing group's first member — quadratic in the number of strings. The trick that unlocks the fast version: anagrams always produce the same result when you sort their characters, so the sorted string is a natural hash-map key. Bucket every string by its sorted form, and each bucket at the end is one group.

Complexity — best & worst case

Brute force — time O(n² · k log k), n = number of strings, k = max string length

Optimal — time O(n · k log k), best and worst case are the same — every string must be sorted once

Optimal — space O(n · k)

Code

// Given an array of strings, group the anagrams together.
// Order of groups/output doesn't matter.

// --- Brute force: compare every string against every group's first member ---
function groupAnagramsBrute(strs) {
  const groups = [];
  const isAnagram = (a, b) => a.split("").sort().join("") === b.split("").sort().join("");

  for (const str of strs) {
    const group = groups.find((g) => isAnagram(g[0], str));
    if (group) group.push(str);
    else groups.push([str]);
  }
  return groups;
}

// --- Optimal: use the sorted string as a hash-map key ---
// Anagrams always produce the same sorted string, so it's a natural
// bucket key — O(n * k log k) instead of O(n^2 * k log k).
function groupAnagrams(strs) {
  const groups = new Map();

  for (const str of strs) {
    const key = str.split("").sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(str);
  }
  return [...groups.values()];
}

// --- Example Usage ---
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]
console.log(groupAnagramsBrute(["eat", "tea", "tan", "ate", "nat", "bat"]));
// same grouping, slower to compute