49. Group Anagrams

In this tutorial we will solve 49. Group Anagrams from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 49. Group Anagrams

Similar problems: 242. Valid Anagram

Problem statement

In this problem we have an input array of strings strs. We have to group the anagrams together and we can return the result in any order.

Example from leetcode.

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

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

Example 3:
Input: strs = ["a"]
Output: [["a"]]

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

In example 1, the strings ["nat","tan"] are anagram so they are grouped together. Similarly, ["ate","eat","tea"] are group of anagrams. The string ["bat"] has no other anagram so it is alone.

Approach

To solve this problem we will use a hash map. The key of the hash map will be the sorted string from the strs array. The value will be an array of anagrams.

Let's solve the input string strs = ["eat","tea","tan","ate","nat","bat"].

hashmap = {}

index =  0       1       2       3       4       5
strs  = ["eat",  "tea",  "tan",  "ate",  "nat",  "bat"]
          ^
sort("eat") = aet
aet is not in the hashmap, add new entry.
hashmap = {
  "aet": ["eat"]
}


index =  0       1       2       3       4       5
strs  = ["eat",  "tea",  "tan",  "ate",  "nat",  "bat"]
                  ^
sort("tea") = aet
aet is in the hashmap, append entry.
hashmap = {
  "aet": ["eat", "tea"]
}


index =  0       1       2       3       4       5
strs  = ["eat",  "tea",  "tan",  "ate",  "nat",  "bat"]
                          ^
sort("tan") = ant
ant is not in the hashmap, add new entry.
hashmap = {
  "aet": ["eat", "tea"],
  "ant": ["tan"]
}


index =  0       1       2       3       4       5
strs  = ["eat",  "tea",  "tan",  "ate",  "nat",  "bat"]
                                  ^
sort("ate") = aet
aet is in the hashmap, append entry.
hashmap = {
  "aet": ["eat", "tea", "ate"],
  "ant": ["tan"]
}


index =  0       1       2       3       4       5
strs  = ["eat",  "tea",  "tan",  "ate",  "nat",  "bat"]
                                          ^
sort("nat") = ant
ant is in the hashmap, append entry.
hashmap = {
  "aet": ["eat", "tea", "ate"],
  "ant": ["tan", "nat"]
}


index =  0       1       2       3       4       5
strs  = ["eat",  "tea",  "tan",  "ate",  "nat",  "bat"]
                                                  ^
sort("bat") = abt
abt is not in the hashmap, add new entry.
hashmap = {
  "aet": ["eat", "tea", "ate"],
  "ant": ["tan", "nat"],
  "abt": ["bat"]
}

The group of anagrams for the above input is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Code

JavaScript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  let hm = new Map();
  for(let str of strs) {
    const sortedString = str.split('').sort().join('');
    if (!hm.has(sortedString)) {
        hm.set(sortedString, []);
    }
    hm.get(sortedString).push(str);
  }
  return Array.from(hm.values());
};

Complexity

Time complexity: O(n * klogk)

If the input string array has n elements then we have to go through all the elements. And let us assume the average length of the strings is k.

Therefore, to sort the string of k length we will have the time complexity of O(klogk). And we have n elements so the total time complexity will be O(n * klogk).

Space complexity: O(n * k)

In the worst case, our hash map will save n elements. And if the average string length is k then the space complexity will be O(n * k).