Group Anagrams

Group Anagrams

What is this problem about?

The Group Anagrams interview question is one of the most frequently asked coding problems. You are given an array of strings. Your task is to group the anagrams together. An anagram is a word formed by rearranging the letters of another word (e.g., "eat" and "tea"). You can return the groups in any order.

Why is this asked in interviews?

This problem is universally asked by almost every tech company (Amazon, Google, Microsoft, Apple, etc.) as a fundamental test of Hash Table and String manipulation skills. It evaluates a candidate's ability to identify a "canonical representation" (a unique signature) for a set of related data and use it as a key in a dictionary to group items efficiently.

Algorithmic pattern used

This problem relies heavily on the Hash Map Grouping pattern. To group anagrams, you need a key that is identical for all anagrams of the same word.

1. Sorting: Sort the characters of the string. "eat", "tea", and "ate" all sort to "aet". Use "aet" as the key in a Hash Map, and append the original strings to a list associated with that key.
2. Frequency Count (Optimal): Instead of sorting ($O(K \log K)$ per word), create an array of size 26 to count character frequencies. Convert this frequency array into a string or tuple (e.g., "1#0#0...1#1...") and use it as the map key. This reduces the time per word to $O(K)$.

Example explanation

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

1. "eat" -> sorted: "aet". Map: {"aet": ["eat"]}
2. "tea" -> sorted: "aet". Map: {"aet": ["eat", "tea"]}
3. "tan" -> sorted: "ant". Map: {"aet": ["eat", "tea"], "ant": ["tan"]}
4. "ate" -> sorted: "aet". Map: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]} ...and so on. Return the values of the map as a list of lists.

Common mistakes candidates make

• O(N^2) comparisons: Trying to compare every string with every other string using a helper isAnagram function. This is extremely slow for large arrays.
• Un-hashable Keys: In languages like Java or Python, trying to use a raw array (like int[26]) directly as a Hash Map key without converting it to a string or a tuple first, resulting in reference-based hashing rather than value-based hashing.

Interview preparation tip

Always implement the Sorting approach first as it's cleaner and easier to explain. Once you have that working, tell the interviewer: "I can optimize the $O(K \log K)$ string sorting to $O(K)$ using a character frequency array as the hash key." This shows progression and deep understanding.