Group Anagrams medium

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

Input: strs = [""] Output: [[]]

Steps

1. Create a map: Use a Map to store the anagrams. The key will be a sorted string representation of each word (since anagrams have the same letters, just rearranged), and the value will be an array of strings representing the anagrams with that key.

2. Iterate through the input array: For each string in the input array strs:

   • Sort the string alphabetically.
   • Use the sorted string as the key in the map.
   • If the key exists, add the original string to the array associated with that key.
   • If the key doesn't exist, create a new entry in the map with the sorted string as the key and an array containing the original string as the value.

3. Extract the values: Finally, extract all the values (arrays of anagrams) from the map and return them as the result.

Explanation

The core idea is to use a sorted string as a unique identifier for each group of anagrams. Sorting the characters of each word ensures that anagrams will always have the same sorted representation, regardless of the order of their letters. The Map data structure provides efficient lookups and insertion for grouping the anagrams.

Code

function groupAnagrams(strs: string[]): string[][] {
    const anagramMap = new Map<string, string[]>();

    for (const str of strs) {
        const sortedStr = str.split('').sort().join(''); // Sort the string alphabetically
        if (anagramMap.has(sortedStr)) {
            anagramMap.get(sortedStr)!.push(str); // Add to existing array
        } else {
            anagramMap.set(sortedStr, [str]); // Create new array
        }
    }

    return Array.from(anagramMap.values()); // Extract values from the map
}

Complexity

• Time Complexity: O(M * N * log N), where N is the average length of the strings, and M is the number of strings. The dominant factor is the sorting of each string (O(N * log N)), which is repeated for each of the M strings.

• Space Complexity: O(M * N) in the worst case, where M is the number of strings and N is the average length of a string. This is because in the worst-case scenario (all strings are anagrams of each other), the map will store all the strings. The space used by the map is proportional to the total number of characters in all the strings.