Mental Model

Group words that have the same letters by sorting their letters and using that as a key.

Analogy: Imagine sorting letters of each word like arranging colored beads in order; words with the same bead order belong to the same group.

words: [eat, tea, tan, ate, nat, bat]
keys:  [aet, aet, ant, aet, ant, abt]

Hash Map:
{
  "aet" -> [eat, tea, ate]
  "ant" -> [tan, nat]
  "abt" -> [bat]
}

Dry Run Walkthrough

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

Goal: Group words that are anagrams together using a hash map keyed by sorted letters.

Step 1: Take first word 'eat', sort letters to get 'aet', add 'eat' to group 'aet'

{ "aet": [eat] }

Why: Sorting letters creates a key that groups anagrams together

Step 2: Take second word 'tea', sort letters to get 'aet', add 'tea' to group 'aet'

{ "aet": [eat, tea] }

Why: Words with same sorted letters belong to same group

Step 3: Take third word 'tan', sort letters to get 'ant', add 'tan' to group 'ant'

{ "aet": [eat, tea], "ant": [tan] }

Why: New sorted key creates a new group

Step 4: Take fourth word 'ate', sort letters to get 'aet', add 'ate' to group 'aet'

{ "aet": [eat, tea, ate], "ant": [tan] }

Why: Add to existing group with same key

Step 5: Take fifth word 'nat', sort letters to get 'ant', add 'nat' to group 'ant'

{ "aet": [eat, tea, ate], "ant": [tan, nat] }

Why: Add to existing group with same key

Step 6: Take sixth word 'bat', sort letters to get 'abt', add 'bat' to group 'abt'

{ "aet": [eat, tea, ate], "ant": [tan, nat], "abt": [bat] }

Why: New key creates new group

Result:

{ "aet": [eat, tea, ate], "ant": [tan, nat], "abt": [bat] }

Annotated Code

DSA C

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

// Node for linked list of words
typedef struct WordNode {
    char *word;
    struct WordNode *next;
} WordNode;

// Hash map entry
typedef struct Entry {
    char *key; // sorted letters
    WordNode *words; // linked list of words
    struct Entry *next;
} Entry;

#define HASH_SIZE 101

// Hash map with chaining
typedef struct HashMap {
    Entry *buckets[HASH_SIZE];
} HashMap;

unsigned int hash_func(const char *str) {
    unsigned int hash = 0;
    while (*str) {
        hash = hash * 31 + (unsigned char)(*str++);
    }
    return hash % HASH_SIZE;
}

// Create a new word node
WordNode *create_word_node(const char *word) {
    WordNode *node = malloc(sizeof(WordNode));
    node->word = strdup(word);
    node->next = NULL;
    return node;
}

// Create a new entry
Entry *create_entry(const char *key, const char *word) {
    Entry *entry = malloc(sizeof(Entry));
    entry->key = strdup(key);
    entry->words = create_word_node(word);
    entry->next = NULL;
    return entry;
}

// Insert word into hash map
void insert(HashMap *map, const char *word) {
    int len = strlen(word);
    char *sorted = malloc(len + 1);
    strcpy(sorted, word);
    // Sort letters to get key
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (sorted[i] > sorted[j]) {
                char temp = sorted[i];
                sorted[i] = sorted[j];
                sorted[j] = temp;
            }
        }
    }

    unsigned int index = hash_func(sorted);
    Entry *entry = map->buckets[index];

    // Search for existing key
    while (entry) {
        if (strcmp(entry->key, sorted) == 0) {
            // Add word to this entry's list
            WordNode *wn = create_word_node(word);
            wn->next = entry->words;
            entry->words = wn;
            free(sorted);
            return;
        }
        entry = entry->next;
    }

    // Key not found, create new entry
    Entry *new_entry = create_entry(sorted, word);
    new_entry->next = map->buckets[index];
    map->buckets[index] = new_entry;
    free(sorted);
}

// Print groups of anagrams
void print_groups(HashMap *map) {
    for (int i = 0; i < HASH_SIZE; i++) {
        Entry *entry = map->buckets[i];
        while (entry) {
            WordNode *wn = entry->words;
            printf("[");
            while (wn) {
                printf("%s", wn->word);
                if (wn->next) printf(", ");
                wn = wn->next;
            }
            printf("]\n");
            entry = entry->next;
        }
    }
}

// Free memory
void free_map(HashMap *map) {
    for (int i = 0; i < HASH_SIZE; i++) {
        Entry *entry = map->buckets[i];
        while (entry) {
            Entry *next_entry = entry->next;
            free(entry->key);
            WordNode *wn = entry->words;
            while (wn) {
                WordNode *next_wn = wn->next;
                free(wn->word);
                free(wn);
                wn = next_wn;
            }
            free(entry);
            entry = next_entry;
        }
    }
}

int main() {
    const char *words[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    int n = sizeof(words) / sizeof(words[0]);

    HashMap map = {0};

    for (int i = 0; i < n; i++) {
        insert(&map, words[i]);
    }

    print_groups(&map);

    free_map(&map);
    return 0;
}

for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (sorted[i] > sorted[j]) { char temp = sorted[i]; sorted[i] = sorted[j]; sorted[j] = temp; } } }

sort letters of word to create key for grouping anagrams

while (entry) { if (strcmp(entry->key, sorted) == 0) { add word to entry's word list; return; } entry = entry->next; }

search for existing group with same sorted key

create new entry with key and word; insert at bucket head

create new group if key not found

for each word in input array, insert into hash map

build groups by processing all words

print all groups by iterating hash map buckets and word lists

output grouped anagrams

OutputSuccess

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

Complexity Analysis

Time: O(n * k^2) because for each of the n words, sorting k letters takes O(k^2) with simple sort

Space: O(n * k) because storing all words and keys in hash map requires space proportional to input size

vs Alternative: Better than comparing each pair of words O(n^2 * k), hash map groups in near linear time

Edge Cases

empty input array

no groups printed, program runs without error

DSA C

for (int i = 0; i < n; i++) { insert(&map, words[i]); }

words with single letter

each letter forms its own group or groups if repeated

DSA C

sorting loop handles length 1 correctly

words with duplicates (e.g., 'aab', 'aba')

correctly grouped together because sorted key is same

DSA C

sorting and key comparison lines

When to Use This Pattern

When you need to group words that are anagrams, use a hash map keyed by sorted letters to quickly collect groups.

Common Mistakes

Mistake: Using the original word as key instead of sorted letters
Fix: Sort the letters of each word before using as key

Mistake: Not handling collisions in hash map chaining
Fix: Use linked lists to handle multiple entries in same bucket

Summary

Groups words that are anagrams by sorting letters and using a hash map keyed by sorted letters.

Use when you want to collect all anagrams together efficiently from a list of words.

The key insight is that anagrams share the same sorted letter sequence, which can be used as a unique group key.