SimuVedaAlgorithms Lab Open in the lab

Hashing / Intermediate

Group Anagrams Visualizer

Sort the letters of each word. Anagrams give the same sorted key, so a hash map from key to list collects each group in one pass.

Start the Group Anagrams simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n·k log k)
Average timeO(n·k log k)
Worst timeO(n·k log k)
Extra spaceO(n·k)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. An empty map from sorted key to words.
  2. Take "eat".
  3. Sort its letters: key "aet".
  4. "aet" is new: start a group with "eat".
  5. Take "tea".
  6. Sort its letters: key "aet".
  7. "aet" is already a key, so "tea" joins "eat".
  8. Take "tan".
  9. Sort its letters: key "ant".
  10. "ant" is new: start a group with "tan".
  11. Take "ate".
  12. Sort its letters: key "aet".
  13. "aet" is already a key, so "ate" joins "eat", "tea".
  14. Take "nat".
  15. Sort its letters: key "ant".
  16. "ant" is already a key, so "nat" joins "tan".
  17. Take "bat".
  18. Sort its letters: key "abt".
  19. "abt" is new: start a group with "bat".
  20. Done: 3 groups.

Try it with your own input →

Group anagrams in Java, Python, C++, C and JavaScript

List<List<String>> groupAnagrams(String[] words) {
  Map<String, List<String>> groups = new HashMap<>();
  for (String w : words) {
    char[] c = w.toCharArray();
    Arrays.sort(c);
    String key = new String(c);
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
  }
  return new ArrayList<>(groups.values());
}
def group_anagrams(words):
    groups = {}
    for w in words:
        key = ''.join(sorted(w))
        groups.setdefault(key, []).append(w)
    return list(groups.values())
vector<vector<string>> groupAnagrams(const vector<string>& words) {
  unordered_map<string, vector<string>> groups;
  for (const string& w : words) {
    string key = w;
    sort(key.begin(), key.end());
    groups[key].push_back(w);
  }
  vector<vector<string>> out;
  for (auto& [k, g] : groups) out.push_back(g);
  return out;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int byChar(const void* a, const void* b) { return *(const char*)a - *(const char*)b; }

/* Prints each group on one line. The sorted letters are the key; equal keys form a group. */
void groupAnagrams(char* words[], int n) {
  char keys[100][32];
  int done[100] = {0};
  for (int i = 0; i < n; i++) {
    strcpy(keys[i], words[i]);
    qsort(keys[i], strlen(keys[i]), 1, byChar);
  }
  for (int i = 0; i < n; i++) {
    if (done[i]) continue;
    for (int j = i; j < n; j++)
      if (!done[j] && strcmp(keys[i], keys[j]) == 0) { printf("%s ", words[j]); done[j] = 1; }
    printf("|");
  }
}
function groupAnagrams(words) {
  const groups = new Map();
  for (const w of words) {
    const key = [...w].sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}

In an interview

LeetCode 49, Group Anagrams: put words that are anagrams of each other in the same group.

A 26-count signature like "1#0#0#…" also works as a key and avoids the k log k sort. Say which you use and why.

More hashing