Group Anagrams

Mediumarrayhash-tablestringsorting
Category: Array & Hashing
Companies that ask this question:
AmazonFacebookGoogleMicrosoftBloomberg
LeetCode →NeetCode →

Approach

Group Anagrams

Problem

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Approach 1: Sorted String as Key (Optimal)

Intuition

Anagrams have the same characters, just in different order. If we sort each string, anagrams will produce identical sorted strings. We can use this sorted string as a key in a hash map.

Algorithm

def groupAnagrams(strs):
    groups = {}
    for s in strs:
        # Sort the string to create key
        key = ''.join(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    
    return list(groups.values())

Example Walkthrough

For ["eat", "tea", "tan", "ate"]:

  • "eat" → sorted: "aet" → groups["aet"] = ["eat"]
  • "tea" → sorted: "aet" → groups["aet"] = ["eat", "tea"]
  • "tan" → sorted: "ant" → groups["ant"] = ["tan"]
  • "ate" → sorted: "aet" → groups["aet"] = ["eat", "tea", "ate"]

Result: [["eat", "tea", "ate"], ["tan"]]

Time Complexity

  • O(n * k log k): n strings, each of length k, sorting each takes O(k log k)

Space Complexity

  • O(n * k): Storing all strings in hash map

Approach 2: Character Count as Key

Intuition

Instead of sorting, count the frequency of each character. Anagrams have identical character counts.

Algorithm

def groupAnagrams(strs):
    from collections import defaultdict
    groups = defaultdict(list)
    
    for s in strs:
        # Count characters (a-z)
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        # Use tuple of counts as key
        key = tuple(count)
        groups[key].append(s)
    
    return list(groups.values())

Time Complexity

  • O(n * k): n strings, each of length k, counting takes O(k)

Space Complexity

  • O(n * k): Storing all strings

Which Approach to Use?

  • Sorted String Key (Approach 1): Simpler code, good for small strings
  • Character Count Key (Approach 2): Better time complexity O(n*k), optimal for longer strings

Both are commonly accepted in interviews. Choose based on simplicity vs optimization needs.

Solution

java
1/**
2 * Group Anagrams
3 * Time: O(n * k log k) with sorting, O(n * k) with character count
4 * Space: O(n * k)
5 */
6
7import java.util.*;
8
9// Approach 1: Sorted String as Key
10class Solution {
11    public List<List<String>> groupAnagrams(String[] strs) {
12        Map<String, List<String>> groups = new HashMap<>();
13        
14        for (String s : strs) {
15            // Sort the string to create key
16            char[] chars = s.toCharArray();
17            Arrays.sort(chars);
18            String key = new String(chars);
19            
20            if (!groups.containsKey(key)) {
21                groups.put(key, new ArrayList<>());
22            }
23            groups.get(key).add(s);
24        }
25        
26        return new ArrayList<>(groups.values());
27    }
28}
29
30// Approach 2: Character Count as Key (Optimal - O(n*k))
31class Solution2 {
32    public List<List<String>> groupAnagrams(String[] strs) {
33        Map<String, List<String>> groups = new HashMap<>();
34        
35        for (String s : strs) {
36            // Count characters (a-z)
37            int[] count = new int[26];
38            for (char c : s.toCharArray()) {
39                count[c - 'a']++;
40            }
41            
42            // Create key from count array
43            StringBuilder keyBuilder = new StringBuilder();
44            for (int i = 0; i < 26; i++) {
45                keyBuilder.append('#');
46                keyBuilder.append(count[i]);
47            }
48            String key = keyBuilder.toString();
49            
50            if (!groups.containsKey(key)) {
51                groups.put(key, new ArrayList<>());
52            }
53            groups.get(key).add(s);
54        }
55        
56        return new ArrayList<>(groups.values());
57    }
58}
59
60// Approach 3: Using computeIfAbsent
61class Solution3 {
62    public List<List<String>> groupAnagrams(String[] strs) {
63        Map<String, List<String>> groups = new HashMap<>();
64        
65        for (String s : strs) {
66            char[] chars = s.toCharArray();
67            Arrays.sort(chars);
68            String key = new String(chars);
69            
70            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
71        }
72        
73        return new ArrayList<>(groups.values());
74    }
75}
76
Loading visualizer...