Group Anagrams

This one looks tricky the first time you see it. But it is really a question about one thing. Can you find a smart way to tell which words belong together? The interviewer wants to see if you can spot a common signature that every anagram in a group shares. Once you find that signature, the whole problem becomes easy. So let us slow down and figure out what that signature is.

🧩 The Problem

You are given a list of words. You have to group together the words that are anagrams of each other. An anagram is a word made by rearranging the letters of another word. So "eat" and "tea" are anagrams. They use the same letters, just in a different order.

Here is what the input and output look like:

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

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

See how "eat", "tea", and "ate" all sit in one group? They are all built from the letters e, a, and t. The order of the groups does not matter. The order inside a group does not matter either. We just need the right words bunched together.

🐢 The Brute Force Idea

The first idea that comes to mind is to compare every word with every other word. Take one word. Then walk through all the rest. For each one, check “are you an anagram of me?”. If yes, drop it into the same group.

But how do you even check if two words are anagrams? You would sort both words and see if they match. Or count their letters. Either way, you do this check for every pair of words. That is a lot of comparing.

If you have n words, comparing every word with every other word is already O(n²). And each comparison costs extra time on top. So this gets slow fast when the list is big. The interviewer will nod, but then ask the real question. “Can you do better?”

⚡ The Smart Idea: A Sorted Key

Now here is the trick that makes this click. Think about what is the same for every word in a group. The letters are the same. Only the order is different. So what if we remove the order?

If you take "eat" and sort its letters, you get "aet". If you take "tea" and sort its letters, you also get "aet". And "ate" sorted is "aet" too. See the pattern? Every anagram, once sorted, turns into the exact same string. That sorted string is our signature. It is the secret label that all members of a group share.

So now we use a hash map. A hash map is a structure that stores key and value pairs. The key will be the sorted word. The value will be the list of all words that sorted to that key. We go through each word once. We sort it to get the key. Then we push the original word into the bucket for that key. At the end, every bucket is one group of anagrams.

"eat" -> sort -> "aet"  ->  bucket["aet"] = ["eat"]
"tea" -> sort -> "aet"  ->  bucket["aet"] = ["eat", "tea"]
"tan" -> sort -> "ant"  ->  bucket["ant"] = ["tan"]
"ate" -> sort -> "aet"  ->  bucket["aet"] = ["eat", "tea", "ate"]
"nat" -> sort -> "ant"  ->  bucket["ant"] = ["tan", "nat"]
"bat" -> sort -> "abt"  ->  bucket["abt"] = ["bat"]

📝 Steps to Group Anagrams

1. Create an empty hash map. The key is a sorted word. The value is a list of words.
2. Go through each word in the input list, one by one.
3. Sort the letters of the word to make the key.
4. Look up that key in the map. If it is missing, start a new empty list for it.
5. Add the original word to the list for that key.
6. After the loop, collect all the values from the map. Each value is one group.

💻 The Code

Here is the optimal solution in all five languages. Each one builds the map, then prints every group.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Compare function used to sort the characters of a word.
int cmpChar(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}

int main(void) {
    char *words[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    int n = 6;

    // keys[i] holds the sorted version of words[i].
    char keys[6][16];
    for (int i = 0; i < n; i++) {
        strcpy(keys[i], words[i]);
        qsort(keys[i], strlen(keys[i]), sizeof(char), cmpChar);
    }

    int used[6] = {0}; // marks words already placed in a group

    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        printf("[ %s", words[i]);
        used[i] = 1;
        // Find every later word with the same sorted key.
        for (int j = i + 1; j < n; j++) {
            if (!used[j] && strcmp(keys[i], keys[j]) == 0) {
                printf(", %s", words[j]);
                used[j] = 1;
            }
        }
        printf(" ]\n");
    }
    return 0;
}

[ eat, tea, ate ]
[ tan, nat ]
[ bat ]

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};

    // Key is the sorted word, value is the list of original words.
    unordered_map<string, vector<string>> groups;

    for (const string &word : words) {
        string key = word;
        sort(key.begin(), key.end()); // sort letters to build the key
        groups[key].push_back(word);   // drop word into its bucket
    }

    // Print each group.
    for (const auto &pair : groups) {
        cout << "[ ";
        for (size_t i = 0; i < pair.second.size(); i++) {
            cout << pair.second[i];
            if (i + 1 < pair.second.size()) cout << ", ";
        }
        cout << " ]" << endl;
    }
    return 0;
}

[ bat ]
[ tan, nat ]
[ eat, tea, ate ]

import java.util.*;

public class GroupAnagrams {
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};

        // Key is the sorted word, value is the list of original words.
        // LinkedHashMap keeps the groups in first-seen order.
        Map<String, List<String>> groups = new LinkedHashMap<>();

        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);            // sort letters
            String key = new String(chars); // build the key
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }

        // Print each group.
        for (List<String> group : groups.values()) {
            System.out.println(group);
        }
    }
}

[eat, tea, ate]
[tan, nat]
[bat]

def group_anagrams(words):
    groups = {}  # key: sorted word, value: list of words
    for word in words:
        key = "".join(sorted(word))  # sort letters to build the key
        groups.setdefault(key, []).append(word)  # add word to its bucket
    return list(groups.values())


words = ["eat", "tea", "tan", "ate", "nat", "bat"]
for group in group_anagrams(words):
    print(group)

['eat', 'tea', 'ate']
['tan', 'nat']
['bat']

function groupAnagrams(words) {
  const groups = new Map(); // key: sorted word, value: list of words
  for (const word of words) {
    const key = word.split("").sort().join(""); // build the sorted key
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word); // add word to its bucket
  }
  return Array.from(groups.values());
}

const words = ["eat", "tea", "tan", "ate", "nat", "bat"];
for (const group of groupAnagrams(words)) {
  console.log(group);
}

[ 'eat', 'tea', 'ate' ]
[ 'tan', 'nat' ]
[ 'bat' ]

⏱️ Time and Space Complexity

Let n be the number of words and k be the length of the longest word.

For each word we sort its letters, and sorting one word of length k costs O(k log k). We do that for all n words. So the total time is O(n · k log k). The space is O(n · k) because in the worst case the map holds every word.

🧩 Key Takeaways

• ✅ All anagrams share the same letters, so sorting any of them gives the same string. That sorted string is the perfect group key.
• ✅ A hash map lets you bucket words by their sorted key in one pass through the list.
• ✅ The sorted-key approach runs in O(n · k log k), much faster than comparing every pair.
• ✅ For lowercase-only words, a 26-letter count key drops the cost to O(n · k).
• ✅ Group order in the output does not matter. Only the grouping itself matters.

🚀 What’s Next?

• Check Anagram
• Hash Maps and Dictionaries