Problem Description

You are given an array of strings. The goal is to group the anagrams together.

An anagram is a word formed by rearranging the letters of another word, using all original letters exactly once.

Example 1:

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

Example 2:

Input: [""]
Output: [[""]]

Example 3:

Input: ["a"]
Output: [["a"]]

Approach

The core idea is to recognize that all anagrams share the same sorted version of their characters. For example:

• “eat”, “tea”, and “ate” all become “aet” when sorted.

• “tan” and “nat” both become “ant”.

We can use this sorted version as a unique key in a hash map (unordered_map in C++) to group words that are anagrams of each other.

Steps:

1. Initialize an empty unordered map where:

   • Key: sorted version of the word.

   • Value: a list of strings (all anagrams matching this key).

2. Iterate over each word in the input list:

   • Sort the word alphabetically.

   • Insert the original word into the map using the sorted word as the key.

3. Return the values (grouped anagrams) from the map.

C++ Implementation with Explanation

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;

        for (string word : strs) {
            string key = word;                  // Copy the word
            sort(key.begin(), key.end());       // Sort characters alphabetically
            groups[key].push_back(word);        // Group by sorted key
        }

        vector<vector<string>> result;
        for (auto& pair : groups) {
            result.push_back(pair.second);      // Add each group to the final result
        }

        return result;
    }
};

Time and Space Complexity

Time Complexity:

• Sorting each word takes O(k log k), where k is the length of the word.

• For n words, total time = O(n * k log k).

Space Complexity:

• O(n * k), due to storing all the input words in the hash map and result vector.

Why This Solution Is Effective

• It uses a simple, well-known technique (sorting + hashing).

• Easy to understand and implement.

• Efficient enough for the given constraints.

Relevance

This question has been asked in real software engineering interviews at Amazon. It tests the candidate’s ability to work with strings, sorting, and hash maps efficiently.