Blind 75| Group Anagrams javascript solution (string sorting approach)

Hello fellow developers ✋! In this article, we will cover how to solve Group Anagrams with two approaches.

Question — In this question, we have an array of strings. and we want to return an output where strings are groups by anagrams.

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

What is Anagram? — a word, phrase, or name formed by rearranging the letters of another. for eg “eat” can be rearranged to create “ate” or “tea”.

Approach — This can be done by sorting strings right? Yes, we can sort every string for eg 👇

let str = "eat"
let sortedStr = [...str] //string to array ["e","a","t"]
                   .sort() //sorting it to look like ["a","e","t"]
                   .join("") // will get "aet" as sortedStr value

Now that we have sorted the string of every input string, we need something to store that string so that we can add or retrieve data effectively. Here we can use simple Object or Map datatype. Map datatype comes with predefined getters and setters which we can leverage easily but for now, we will use Object type for simplicity.

Also, we will use for loop to iterate over the given array of strings

function groupAnagrams(strs) {
   const map = {}; // Object to store data for eg. {"aet":["eat","ate"]}
    for(let i=0;i<strs.length;i++){
      let sortedStr = [...strs[i]].sort().join("");
// Now that we have sorted string we can check if the string is already present in map object or not in below lines of code.
      if(map[sortedStr]){
           map[sortedStr] = [...map[sortedStr],strs[i]];
       }else{
           map[sortedStr] = [strs[i]];
       }
    }
}

Here we are treating sortedStr as a key in map object and every key corresponds to an array of strings. for eg. {“aet”:[“eat”,”ate”]}

if(map[sortedStr]){
      // if key exists then add current string to the map
      map[sortedStr] = [...map[sortedStr],strs[i]];
 }else{
     // if key doesn’t exists then create an array and add first entry as string to the map.
     map[sortedStr] = [strs[i]];
 }

Now we are pretty much done with the solution! One last thing we have to do is to return the values we stored in the map Object as key-value pair to the array of grouped strings. We can easily do this with the Object’s values() function with the object spread operator.

return [...Object.values(map)]

Finally, our code looks like this

function groupAnagrams(strs){
  const map = {}; 
  for(let i=0;i<strs.length;i++){
      let sortedStr = [...strs[i]].sort().join("") 
                             
         if( map[sortedStr]){
           map[sortedStr] = [...map[sortedStr],strs[i]]
         } else{
           map[sortedStr] = [strs[i]]
         }                
    }
    return [...Object.values(map)]
}

Now let’s discuss the Elephant in the room! Yes, the complexity of this solution —

Since we are sorting every string. let’s consider this as a nlogn, where n denotes the average length of the string.

Also, we are iterating over a given array of strings. let’s consider this as m.

So we can consider time complexity as m*nlogn and space complexity as m*n

 m - length of strs;
 n - average length of the string
 Time: O(m * nlog n)
 Space: O(m * n)

Yes, we can do better than this in terms of time complexity and I will cover that in the next part of this blog. If you have any questions regarding this or anything I should update in the above solution, feel free to comment or DM me.

👏 Clap if you like this article!!!