Group Anagrams Using Hash Map in DSA Java - Execution Trace

Concept Flow - Group Anagrams Using Hash Map

Start with list of words

↓

Take one word from list

↓

Sort letters of the word

↓

Use sorted word as key in hash map

↓

Add original word to list at this key

↓

Repeat for all words

↓

Collect all lists from hash map

↓

Return grouped anagrams

We take each word, sort its letters to create a key, then group words with the same key in a hash map.

Execution Sample

DSA Java

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
map = {}
for word in words:
  key = ''.join(sorted(word))
  map.setdefault(key, []).append(word)
result = list(map.values())
return result

This code groups words that are anagrams by sorting letters and using the sorted word as a key in a hash map.

Execution Table

Step	Operation	Word Processed	Sorted Key	Hash Map State	Visual State
1	Process word	eat	aet	{"aet": ["eat"]}	[aet] -> eat
2	Process word	tea	aet	{"aet": ["eat", "tea"]}	[aet] -> eat -> tea
3	Process word	tan	ant	{"aet": ["eat", "tea"], "ant": ["tan"]}	[aet] -> eat -> tea | [ant] -> tan
4	Process word	ate	aet	{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}	[aet] -> eat -> tea -> ate | [ant] -> tan
5	Process word	nat	ant	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}	[aet] -> eat -> tea -> ate | [ant] -> tan -> nat
6	Process word	bat	abt	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}	[aet] -> eat -> tea -> ate | [ant] -> tan -> nat | [abt] -> bat
7	Collect groups	-	-	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	[Group1] eat, tea, ate | [Group2] tan, nat | [Group3] bat
8	Return result	-	-	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	[Group1] eat, tea, ate | [Group2] tan, nat | [Group3] bat

💡 All words processed and grouped by their sorted keys in the hash map.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
word	-	eat	tea	tan	ate	nat	bat	-
key	-	aet	aet	ant	aet	ant	abt	-
hash_map	{}	{"aet": ["eat"]}	{"aet": ["eat", "tea"]}	{"aet": ["eat", "tea"], "ant": ["tan"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

Key Moments - 3 Insights

Why do we sort the word to create the key?

Sorting the word arranges letters in order, so all anagrams have the same sorted key. See execution_table steps 1 and 2 where 'eat' and 'tea' both map to 'aet'.

What happens if a key is not yet in the hash map?

We create a new list for that key and add the word. In execution_table step 1, 'aet' key is created with ['eat'] because it was not present before.

How do we know when all groups are ready to return?

After processing all words (step 6), the hash map has all groups. Step 7 collects these groups for the final output.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the hash map state?

A {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}

B {"aet": ["eat", "tea"], "ant": ["tan"]}

C {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}

D {"aet": ["eat"], "ant": ["tan"]}

💡 Hint

Check the hash map state column at step 4 in the execution_table.

At which step does the key 'abt' first appear in the hash map?

A Step 3

B Step 6

C Step 5

D Step 7

💡 Hint

Look for when 'bat' is processed and added to the hash map in execution_table.

If the word 'tab' was added after 'bat', which key would it map to in the hash map?

A "tab"

B "bat"

C "abt"

D "tba"

💡 Hint

Remember the key is the sorted letters of the word, see variable_tracker for key values.

Concept Snapshot

Group Anagrams Using Hash Map:
- Sort each word's letters to create a key.
- Use the key in a hash map to group words.
- Append words to the list at their key.
- After all words, collect all groups from the map.
- Returns list of anagram groups.

Full Transcript

This concept groups words that are anagrams by sorting each word's letters to create a key. We use a hash map where each key is the sorted word, and the value is a list of words matching that key. We process each word, sort it, and add it to the corresponding list in the map. After processing all words, we collect all lists from the map as groups of anagrams. The execution table shows each step adding words to the map and the evolving state. The variable tracker follows the word, key, and hash map changes. Key moments clarify why sorting is used, how new keys are created, and when the final groups are ready. The visual quiz tests understanding of the hash map state at different steps and the key creation logic.

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