Coding problem · Medium · Arrays & Hashing

Group Anagrams

Medium Algorithms & data structures Most askedSeen at Amazon, Meta, Microsoft, Goldman Sachs

Given an array of strings strs, group the anagrams together. You can return the groups, and the words inside each group, in any order.

Example 1

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

Constraints

1 <= strs.length <= 10^4
Words contain lowercase letters

Hints

Hint 1

Anagrams share a canonical key. What key is identical for 'eat' and 'tea'?

Hint 2

Use the sorted word (or a 26-letter count signature) as a hash-map key.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n·k log k) where k is the word length · Space O(n·k)

Map each word to a canonical key — its letters sorted — and append it to that key's bucket. The buckets are the answer. A 26-count tuple key avoids the O(k log k) sort per word.

Reference solution

function groupAnagrams(strs) {
  const groups = new Map();
  for (const w of strs) {
    const key = [...w].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of strs) {
    const key = [...w].sort().join("");
    groups.set(key, [...(groups.get(key) ?? []), w]);
  }
  return [...groups.values()];
}

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for w in strs:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

<?php

function groupAnagrams(array $strs): array
{
    $groups = [];
    foreach ($strs as $w) {
        $chars = str_split($w);
        sort($chars);
        $groups[implode('', $chars)][] = $w;
    }
    return array_values($groups);
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : strs) {
            char[] c = w.toCharArray();
            Arrays.sort(c);
            groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }
}