Group Anagrams Using Hash Map in DSA Java

Mental Model

Group words that have the same letters by sorting their letters and using that as a key.

Analogy: Imagine sorting letters of each word like putting puzzle pieces in order; words with the same pieces in the same order belong to the same box.

words: [eat, tea, tan, ate, nat, bat]
keys:  [aet, aet, ant, aet, ant, abt]
HashMap:
  aet -> [eat, tea, ate]
  ant -> [tan, nat]
  abt -> [bat]

Dry Run Walkthrough

Input: words: [eat, tea, tan, ate, nat, bat]

Goal: Group words that are anagrams together using a hash map

Step 1: Take 'eat', sort letters to get 'aet', add 'eat' to map under key 'aet'

HashMap: { 'aet' -> [eat] }

Why: Sorted letters create a unique key for anagram groups

Step 2: Take 'tea', sort letters to get 'aet', add 'tea' to existing list under 'aet'

HashMap: { 'aet' -> [eat, tea] }

Why: Words with same sorted letters belong to same group

Step 3: Take 'tan', sort letters to get 'ant', add 'tan' under new key 'ant'

HashMap: { 'aet' -> [eat, tea], 'ant' -> [tan] }

Why: New sorted key means new group

Step 4: Take 'ate', sort letters to get 'aet', add 'ate' to list under 'aet'

HashMap: { 'aet' -> [eat, tea, ate], 'ant' -> [tan] }

Why: Add to existing anagram group

Step 5: Take 'nat', sort letters to get 'ant', add 'nat' to list under 'ant'

HashMap: { 'aet' -> [eat, tea, ate], 'ant' -> [tan, nat] }

Why: Add to existing anagram group

Step 6: Take 'bat', sort letters to get 'abt', add 'bat' under new key 'abt'

HashMap: { 'aet' -> [eat, tea, ate], 'ant' -> [tan, nat], 'abt' -> [bat] }

Why: New sorted key means new group

Result:

Groups:
'aet' -> [eat, tea, ate]
'ant' -> [tan, nat]
'abt' -> [bat]

Annotated Code

DSA Java

import java.util.*;

public class GroupAnagrams {

    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars); // sort letters to create key
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); // add word to group
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> groups = groupAnagrams(input);
        for (List<String> group : groups) {
            System.out.println(group);
        }
    }
}

Arrays.sort(chars); // sort letters to create key

Sort letters of the word to get a unique key for anagram groups

String key = new String(chars);

Convert sorted letters back to string to use as map key

map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); // add word to group

Add original word to the list for this key, creating list if needed

Output

[eat, tea, ate]

[tan, nat]

[bat]

Complexity Analysis

Time: O(n * k log k) because we sort each of the n words of length k

Space: O(n * k) to store all words grouped in the hash map

vs Alternative: Naive approach compares each word with others, O(n^2 * k), much slower than sorting keys

Edge Cases

Empty input array

Returns empty list with no groups

DSA Java

for (String s : strs) {

Single word input

Returns list with one group containing that word

DSA Java

map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);

Words with duplicates

Groups correctly by sorted letters including duplicates

DSA Java

Arrays.sort(chars);

When to Use This Pattern

When you need to group words that are made of the same letters, use sorting as a key in a hash map to group anagrams efficiently.

Common Mistakes

Mistake: Using the original word as key instead of sorted letters
Fix: Sort the letters of the word first to create the key

Mistake: Not creating a new list for a new key before adding words
Fix: Use computeIfAbsent or check if key exists and create list if missing

Summary

Groups words that have the same letters by sorting and hashing.

Use when you want to find all anagrams grouped together quickly.

Sorting letters creates a unique key that identifies anagram groups.

Practice

1. What is the main idea behind grouping anagrams using a hash map?

easy

A. Count the length of each word and group by length

B. Group words by their first letter only

C. Use sorted strings as keys to group words that are anagrams

D. Use the original word as the key in the hash map

Solution

1. Step 1: Understand anagram grouping

   Anagrams are words with the same letters in different orders. Sorting letters gives a unique key for each group.

2. Step 2: Use sorted string as hash map key

   By sorting each word and using it as a key, all anagrams map to the same key and can be grouped together.

3. Final Answer:

   Use sorted strings as keys to group words that are anagrams -> Option C

4. Quick Check:

   Sorted string key = group anagrams [OK]

Hint: Sort each word and use as key to group anagrams [OK]

Common Mistakes:

• Grouping by word length only
• Using original word as key without sorting
• Grouping by first letter only

2. Which of the following Java code snippets correctly initializes a hash map to group anagrams?

easy

A. HashMap map = new HashMap<>();

B. HashMap map = new HashMap<>();

C. Map map = new HashMap<>();

D. Map map = new HashMap<>();

Solution

1. Step 1: Identify correct map types for grouping

   We need keys as strings (sorted words) and values as lists of strings (grouped anagrams).

2. Step 2: Check each option's type correctness

   Map map = new HashMap<>(); uses Map, which is correct. Others have wrong key or value types.

3. Final Answer:

   Map map = new HashMap<>(); -> Option D

4. Quick Check:

   Key=String, Value=List<String> for grouping [OK]

Hint: Use Map for grouping anagrams [OK]

Common Mistakes:

• Using int as key type
• Using String as value instead of List<String>
• Using List<String> as key type

3. What is the output of the following Java code snippet?

String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
Map map = new HashMap<>();
for (String word : words) {
  char[] chars = word.toCharArray();
  Arrays.sort(chars);
  String key = new String(chars);
  map.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
System.out.println(map.values());

medium

A. [[eat, tea, ate], [tan, nat], [bat]]

B. [[eat, tea], [tan, nat], [bat, ate]]

C. [[eat, ate], [tea, tan], [nat, bat]]

D. [[eat], [tea], [tan], [ate], [nat], [bat]]

Solution

1. Step 1: Sort each word to get keys

   "eat", "tea", "ate" all sort to "aet"; "tan", "nat" to "ant"; "bat" to "abt".

2. Step 2: Group words by sorted keys

   Words with key "aet" grouped: [eat, tea, ate]; key "ant": [tan, nat]; key "abt": [bat].

3. Final Answer:

   [[eat, tea, ate], [tan, nat], [bat]] -> Option A

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

Hint: Sort words, group by sorted key, print grouped lists [OK]

Common Mistakes:

• Not sorting words before grouping
• Adding words to wrong groups
• Printing keys instead of grouped values

4. Identify the error in this Java code for grouping anagrams:

String[] words = {"bat", "tab", "eat"};
Map map = new HashMap<>();
for (String word : words) {
  char[] chars = word.toCharArray();
  String key = new String(chars);
  Arrays.sort(chars);
  map.putIfAbsent(key, new ArrayList<>());
  map.get(key).add(word);
}
System.out.println(map.values());

medium

A. Sorting is done after creating the key, so keys are incorrect

B. Using putIfAbsent instead of computeIfAbsent causes error

C. The map should use List<Integer> instead of List<String>

D. The loop should use a while instead of for

Solution

1. Step 1: Check order of sorting and key creation

   Key is created from chars before sorting, so key is unsorted word.

2. Step 2: Identify impact on grouping

   Since keys are unsorted, anagrams get different keys and won't group correctly.

3. Final Answer:

   Sorting is done after creating the key, so keys are incorrect -> Option A

4. Quick Check:

   Sort before key creation to group correctly [OK]

Hint: Sort chars before creating key string [OK]

Common Mistakes:

• Creating key before sorting chars
• Confusing putIfAbsent with computeIfAbsent
• Wrong map value type

5. Given a list of words, how would you modify the grouping anagrams approach to handle case-insensitive grouping (e.g., "Eat" and "tea" are anagrams)?

hard

A. Use the original word as key without any change

B. Convert each word to lowercase before sorting and using as key

C. Group words by their length only

D. Sort words but keep original case for keys

Solution

1. Step 1: Understand case-insensitive grouping

   To treat "Eat" and "tea" as same group, ignore case by converting all words to lowercase.

2. Step 2: Apply lowercase conversion before sorting

   Convert word to lowercase, then sort chars to create key. This ensures case differences don't split groups.

3. Step 3: Group words using lowercase sorted keys

   Use these keys in hash map to group anagrams regardless of original case.

4. Final Answer:

   Convert each word to lowercase before sorting and using as key -> Option B

5. Quick Check:

   Lowercase + sort = case-insensitive grouping [OK]

Hint: Lowercase words before sorting for case-insensitive groups [OK]

Common Mistakes:

• Not converting to lowercase before sorting
• Using original case keys causing split groups
• Grouping by length instead of letters