# 49. Group Anagrams

LeetCode Problems

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

## Table of Content

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.

Anagram

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. - Wikipedia

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).