Group Anagrams - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'gold';

function visMainFunction(inputStrs) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const strs = new VisArray(...inputStrs);
    const anagramMap = new VisMap().options({ 
        labelExtractionPolicy: (list) => list.join(', ')
    });

    let wordIndex = 0;
    makeVisVariable(wordIndex).registerAsIndexPointer(strs, CURRENT);
    endBatch();

    for (const word of strs) {
        startPartialBatch();
        notification(`
            📌 <b>Processing word:</b> <b>${makeColoredSpan(`"${word}"`, CURRENT_COLOR)}</b><br/>
            • Start with a <b>26-length frequency array</b> (all zeros), one slot per lowercase letter 'a'–'z'.<br/>
            • For each character in ${makeColoredSpan(`"${word}"`, CURRENT_COLOR)}, increment its corresponding position in this array.<br/>
            • After building the array, we <b>join its numbers with commas</b> (e.g., <code>0,1,0,2,...</code>) to form a string —  
            this string becomes the <b>key</b> that uniquely identifies anagrams.
        `);

        // Create a frequency count array for 26 letters
        const freqs = new VisArray(26).fill(0);

        const visWord = new VisArray(...word).options({ label: "Current Word" });
        let charIndex = 0;
        makeVisVariable(charIndex).registerAsIndexPointer(visWord, CURRENT);

        for (const char of word) {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            notification(`
                ✏️ Counting character <b>${makeColoredSpan(`'${char}'`, CURRENT_COLOR)}</b><br/>
                • ${makeColoredSpan(`'${char}'`, CURRENT_COLOR)} maps to index <b>${index}</b> in the frequency array (0 → 'a', 1 → 'b', ...).<br/>
                • Incrementing that slot to record another occurrence of ${makeColoredSpan(`'${char}'`, CURRENT_COLOR)} in ${makeColoredSpan(`"${word}"`, CURRENT_COLOR)}.
            `);
            freqs[index]++;
            charIndex += 1;
        }

        const key = freqs.join(','); // Convert array to a string key

        notification(`
            🔑 <b>Computed key for ${makeColoredSpan(`"${word}"`, CURRENT_COLOR)}:</b> <code>${key}</code><br/>
            • This key encodes the full frequency distribution of the word’s letters.<br/>
            • All anagrams of ${makeColoredSpan(`"${word}"`, CURRENT_COLOR)} will produce the <b>exact same key</b>.
        `);

        if (!anagramMap.has(key)) {
            notification(`
                🆕 <b>No existing group</b> found for key <code>${key}</code>.<br/>
                • Creating a new group for this combination of character counts.
            `);
            anagramMap.set(key, []);
        } else {
            notification(`
                ♻️ <b>Existing group found</b> for key <code>${key}</code>.<br/>
                • ${makeColoredSpan(`"${word}"`, CURRENT_COLOR)} shares this key with previous words — they are anagrams.<br/>
                • Adding it to the same group.
            `);
        }

        anagramMap.get(key).push(word);

        // The following line updates the visualization of the group in the VisMap.
        anagramMap.set(key, anagramMap.get(key)); // 🔄 Ensuring visualization reflects the updated list.

        notification(`
            ✅ <b>Added:</b> ${makeColoredSpan(`"${word}"`, CURRENT_COLOR)} is now grouped under key <code>${key}</code>.<br/>
            • All words under this key are <b>anagrams of each other</b>.
        `);
        
        wordIndex += 1;
        visWord.destroyVis();
        freqs.destroyVis();
        endBatch();
    }

    notification(`
        🏁 <b>All words processed!</b><br/>
        The <b>final result</b> is the list of grouped words in <code>anagramMap</code> (its values).<br/>
    `);

    return Array.from(anagramMap.values());
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Schema:</b><br/>
        <span class='${CURRENT}' style='background:${CURRENT_COLOR};color:black;'>gold background</span> → 
        Highlights the <b>current word</b> or <b>current character</b> being processed.<br/>
        As the algorithm iterates:
        <ul>
        <li>The pointer over <b>input words</b> shows which word is currently being grouped.</li>
        <li>The pointer over the <b>current word’s characters</b> shows which character is being counted in the frequency array.</li>
        </ul>
        This helps visualize how each word is analyzed and how its frequency key is formed for grouping anagrams.
    `);
}

function initClassProperties() {
    setClassProperties(CURRENT, {
        backgroundColor: CURRENT_COLOR
    });
}

Approach

The key insight for Grouping Anagrams is that all anagrams share the same letter composition — they contain exactly the same letters with the same frequencies, but possibly in a different order. Therefore, to group anagrams, we need a way to represent this composition uniquely for each word.

A straightforward approach is to sort each word alphabetically and use the sorted string as a key. However, sorting each word takes O(m log m) time (where m is the word’s length), which can be costly for large inputs. Instead, we use a more direct method — a frequency-based key that captures the count of each letter efficiently in a single linear pass.

In this optimized approach, every word is represented by a 26-length frequency array (for 'a'–'z'), where each index corresponds to a letter’s count. The array is then joined into a comma-separated string (e.g. "1,0,2,0,...") to serve as a unique key in a HashMap. All anagrams produce the same frequency key, so they are automatically grouped together.

Step 1 — Build frequency key: For each word, compute its 26-length frequency array and convert it into a string key using array.join(',').
Step 2 — Group words: Store each word under its frequency key in a HashMap. Words sharing identical keys have identical character frequencies → they’re anagrams.
Step 3 — Output: Return the map’s values — each list represents one anagram group.

Why this works: Two words are anagrams if and only if they have identical character frequency distributions. Using the frequency key ensures that all anagrams share the same key, while non-anagram words always produce distinct keys.

Time Complexity

Let n be the number of input words and m be the maximum length of a single word.

For each word: We build a 26-length frequency array by scanning its characters once. This takes O(m) time.
Build the key: We join the 26 counts into a comma-separated string. This is O(26) = O(1) per word.
Insert in the map: Looking up and updating the hash map with that key is O(1) on average.

We repeat this for all n words, so the total runtime is O(n · m).

Space Complexity

Let n be the number of input words and m be the average length of each word. The algorithm’s space usage grows in proportion to the total input size, or O(n · m).

Grouping structure: Each word is stored exactly once in the hash map under its frequency key → O(n · m) total space.
Key representation: Each word’s frequency key has a fixed size of 26 integers (for 'a'–'z'), so total key storage adds only O(n) space.
Temporary workspace: A constant-size (26-slot) frequency array is built for each word during processing → O(1) per iteration.

In summary: The overall space complexity is O(n · m), dominated by storing all input words and their groupings in the map.

Input-1

Group Anagrams - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity