Group Anagrams

Words

Current Word

Frequency Array (a-z)

Hash Key (tuple)

HashMap (frequency → words)

Empty

Word Index

Current Word

Char Scanning

Groups Found

Click "Step" or "Play" to start the visualization

Current Word

Processed

Grouped

Python Code
                    group = defaultdict(list)
                
                    for word in strs:
                
                        hash = [0] * 26
                
                        for ch in word:
                
                            hash[ord(ch) - ord("a")] += 1
                
                        group[tuple(hash)].append(word)
                
                    return list(group.values())

Complexity Analysis

Time Complexity O(n · k) Space Complexity O(n · k)

Time Complexity: O(n · k)

Breakdown

Iterate through n words in the input list
For each word, scan k characters to build frequency array: O(k)
Tuple creation from 26-element array: O(26) = O(1)
HashMap lookup and insertion: O(1) amortized

T(n, k) = n × (k + 26 + 1) = O(n · k)

Mathematical Intuition

The sorting-based approach sorts each word's characters in O(k log k), yielding O(n · k log k) total. By counting character frequencies instead of sorting, we reduce per-word cost from O(k log k) to O(k), exploiting the fixed 26-letter alphabet as a constant-size domain.

Key Insight

The 26-element frequency array acts as a perfect hash for anagram equivalence — two words are anagrams if and only if they have identical character frequency distributions.

Space Complexity: O(n · k)

Breakdown

HashMap keys: at most n tuples, each fixed size 26 = O(n)
HashMap values: all n words stored, total chars = O(n · k)
Frequency array: O(26) = O(1), reused per word
Output: all words grouped = O(n · k)

S(n, k) = O(n · k) for storing all words in groups

Mathematical Intuition

Every input word must appear in exactly one output group. Since we store all n words in the hashmap, and the total character count across all words is n · k, the space is necessarily O(n · k). The 26-element frequency array adds only O(1) overhead per iteration.

Key Insight

The space is dominated by the output itself — any algorithm that groups n words of average length k must use at least O(n · k) space to store the result.