DEV Community 👩‍💻👨‍💻

NJOKU SAMSON EBERE
NJOKU SAMSON EBERE

Posted on • Updated on

Algorithm 202 (My Interview Question): Grouping Anagrams in 3 Ways

Last year, I had a technical interview and one of the questions was on Anagrams. I solved the problem in 3 ways today and I want to share it with you in a moment.

Question:

Given an array of strings, group anagrams together.

Anagram: These are words that are made up of the same letters but in different orders.

Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

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

If you have been following my Algorithm series, then you are well fortified for this challenge.


groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]);

/*
  [ [ 'ate', 'eat', 'tea' ], [ 'nat', 'tan' ], [ 'bat' ] ]
*/
Enter fullscreen mode Exit fullscreen mode

Prerequisite

  1. String Reversal
  2. Word Anagram
  3. Sentence Anagram
  4. Array Chunking
  5. Array Merging Without Duplicates

Solution

  • .map(), sort(), join(), Set(), forEach(), filter(), push, spread operator
      function groupAnagrams(array) {
        let finalArray = [];

        // rearrange each word to check for anagram
        let rearranged = array.map(element => {
          return [...element].sort().join("");
        });

        // remove duplicates
        let uniqueArray = [...new Set(rearranged)];

        // compare original array with dupliates
        uniqueArray.forEach(word => {
          let chunk = array.filter(char => word === [...char].sort().join(""));

          finalArray.push(chunk.sort());
        });

        return finalArray;
      }
Enter fullscreen mode Exit fullscreen mode
  • for...of...loop, sort(), join(), filter(), push, split(), indexOf()
      function groupAnagrams(array) {
        let finalArray = [];
        let rearranged = [];

        // rearrange each word to check for anagram
        for (element of array) {
          rearranged.push(
            element
              .split("")
              .sort()
              .join("")
          );
        }

        // remove duplicates
        let uniqueArray = rearranged.filter(
          (member, index) => rearranged.indexOf(member) === index
        );

        // compare original array with dupliates
        for (word of uniqueArray) {
          let chunk = [];

          for (char of array) {
            if (
              word ===
              char
                .split("")
                .sort()
                .join("")
            ) {
              chunk.push(char);
            }
          }
          finalArray.push(chunk.sort());
        }
        return finalArray;
      }
Enter fullscreen mode Exit fullscreen mode
  • for...loop, while...loop, sort(), join(), push(), split(), includes()
      function groupAnagrams(array) {
        let finalArray = [];
        let rearranged = [];

        // rearrange each word to check for anagram
        let i = 0;
        while (i < array.length) {
          rearranged.push(
            array[i]
              .split("")
              .sort()
              .join("")
          );
          i++;
        }

        // remove duplicates
        let uniqueArray = [];
        for (let j = 0; j <= rearranged.length; j++) {
          if (!uniqueArray.includes(rearranged[j])) {
            uniqueArray.push(rearranged[j]);
          }
        }

        // compare original array with dupliates
        let counter = 0;
        while (counter < uniqueArray.length) {
          let chunk = [];

          for (let k = 0; k < array.length; k++) {
            if (
              uniqueArray[counter] ===
              array[k]
                .split("")
                .sort()
                .join("")
            ) {
              chunk.push(array[k]);
            }
          }

          if (chunk.length != 0) {
            finalArray.push(chunk.sort());
          }
          counter++;
        }
        return finalArray;
      }
Enter fullscreen mode Exit fullscreen mode

Conclusion

Interview questions like this one we just solved tends to test how far you have dived into algorithm. As you must have noted, the solution to just this problem is built upon other 5 algorithms we have solved in the past. So starting from the basics is very important.

There are many ways to solve problems programmatically. I will love to know other ways you solved yours in the comment section.

Up Next: Algorithm 101: 4 Ways to FizzBuzz a Single Number

If you have questions, comments or suggestions, please drop them in the comment section.

You can also follow and message me on social media platforms.

Twitter | LinkedIn | Github

Thank You For Your Time.

Top comments (6)

Collapse
 
rebusweb profile image
Wojciech Rebis

Great article, and good interview question.
Good work, keep it up! :)

Just wanted to share my approach to this:

function groupAnagrams(anagrams) {
  const wordGroups = anagrams.reduce((groups, anagram) => {
    const word = anagram.split('').sort().join('');
    if (groups[word]) {
      groups[word].push(anagram);
    } else {
      groups[word] = [anagram];
    }
    return groups;
  }, {});

  return Object.values(wordGroups).map(group => group);
} 
Enter fullscreen mode Exit fullscreen mode

What do you think about it?

Collapse
 
ebereplenty profile image
NJOKU SAMSON EBERE Author

Thank you Wojciech. I love your method. It's very clever and coincise. Works perfectly too.

dev-to-uploads.s3.amazonaws.com/i/...

Do you mind explaining what is going on in the reduce() function probably by commenting the code?

Collapse
 
rebusweb profile image
Wojciech Rebis

I thought of reducing array of anagrams to an object which keys will be initial words and values arrays of anagrams from these words.

Thread Thread
 
ganeshshetty195 profile image
Ganesh Shetty

Tried pretty much in the same way

function groupAnagrams(array) {
var reducedObject = array.reduce((acc, cur) => {
var newcur=cur.split('').sort().join('');
if (!acc[newcur]) {
acc[newcur] = [cur]
} else {
acc[newcur] = [...acc[newcur], cur]
}
return acc;
}, {});
return Object.values(reducedObject);
}
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));

Collapse
 
brunooliveira profile image
Bruno Oliveira

Nice! :)

Collapse
 
ebereplenty profile image
NJOKU SAMSON EBERE Author

Bruno, Thank you for taking your time to read through!

In defense of the modern web

I expect I'll annoy everyone with this post: the anti-JavaScript crusaders, justly aghast at how much of the stuff we slather onto modern websites; the people arguing the web is a broken platform for interactive applications anyway and we should start over;

React users; the old guard with their artisanal JS and hand authored HTML; and Tom MacWright, someone I've admired from afar since I first became aware of his work on Mapbox many years ago. But I guess that's the price of having opinions.