Group Anagrams

Problem Statement

Given an array of strings strs, group the anagrams together. Return the groups in any order.

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

Approach 1: Brute Force

Explanation: Compare each string with others by sorting and checking equality.

Time Complexity: O(n² * k log k) where k = max string length

Space Complexity: O(n * k)

groups = []
for each word in strs:
    check if it matches existing sorted word in groups
    if yes, add to that group
    else, create new group
return groups

💡 Think: Compare sorted forms pairwise to cluster matching words together.

Approach 2: Sorting & Hash Map

Explanation: Sort each string, use it as a key in hash map to group anagrams.

Time Complexity: O(n * k log k)

Space Complexity: O(n * k)

map = {}
for word in strs:
    key = sort(word)
    if key not in map:
        map[key] = []
    map[key].append(word)
return list(map.values())

💡 Think: Use sorted(word) as a hash key to bucket anagram groups.

Approach 3: Character Count Hashing (Optimal)

Explanation: Count frequency of each char, convert count to tuple as hash map key.

Time Complexity: O(n * k)

Space Complexity: O(n * k)

map = {}
for word in strs:
    count = [0]*26
    for char in word:
        count[ord(char)-ord('a')]++
    key = tuple(count)
    if key not in map:
        map[key] = []
    map[key].append(word)
return list(map.values())

💡 Think: Hash a 26-count tuple per word to group by identical character frequencies.

Solve on LeetCode