Group Anagrams Using Hash Map in DSA Rust - Execution Trace

Concept Flow - Group Anagrams Using Hash Map

Start with list of words

↓

For each word: Sort letters

↓

Use sorted word as key in hash map

↓

If key exists: Append word to list

↓

If key not exists: Create new list with word

↓

After all words processed

↓

Collect all lists from hash map as grouped anagrams

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

Execution Sample

DSA Rust

use std::collections::HashMap;

let words = ["eat", "tea", "tan", "ate", "nat", "bat"];
let mut map: HashMap<Vec<char>, Vec<&str>> = HashMap::new();
for word in words {
    let mut chars: Vec<char> = word.chars().collect();
    chars.sort_unstable();
    map.entry(chars).or_insert(vec![]).push(word);
}
let result: Vec<Vec<&str>> = map.into_values().collect();

This code groups the input words into lists of anagrams using a hash map keyed by sorted characters.

Execution Table

Step	Operation	Current Word	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	End	-	-	All words grouped by anagrams	Final groups: [eat, tea, ate], [tan, nat], [bat]

💡 All words processed and grouped by their sorted character keys.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
word	-	eat	tea	tan	ate	nat	bat	-
chars (sorted key)	-	aet	aet	ant	aet	ant	abt	-
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"]}	Collected groups

Key Moments - 3 Insights

Why do we sort the characters of each word before using it as a key?

Sorting characters creates a unique key for all anagrams of that word, so they map to the same group in the hash map. See execution_table steps 1 and 2 where 'eat' and 'tea' both have key 'aet'.

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

We create a new list for that key and add the current word. This is shown in execution_table step 1 for key 'aet' and step 3 for key 'ant'.

How do we collect the final groups after processing all words?

We take all the values (lists of words) from the hash map and collect them into a list of groups, as shown in execution_table step 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the hash map state after processing the word 'ate'?

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

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

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

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

💡 Hint

Check the row for step 4 in execution_table under 'Hash Map State'.

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

A Step 3

B Step 6

C Step 5

D Step 7

💡 Hint

Look at the 'Sorted Key' and 'Hash Map State' columns in execution_table to find when 'abt' appears.

If the word 'bat' was processed before 'tan', how would the hash map state change at step 3?

A {"aet": ["eat", "tea"], "abt": ["bat"]}

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

C {"aet": ["eat", "tea"], "abt": ["bat"], "ant": ["tan"]}

D }]"nat"[ :"tna" ,]"aet" ,"tae"[ :"tea"{

💡 Hint

Consider the sorted keys and order of insertion in execution_table and variable_tracker.

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 existing key's list or create new list.
- Collect all lists from the map as grouped anagrams.
- Efficiently groups words with same letters regardless of order.

Full Transcript

To group anagrams, we take each word and sort its letters to create a key. This key is used in a hash map to group words that are anagrams. If the key exists, we add the word to its list; if not, we create a new list. After processing all words, we collect all lists from the hash map as the final groups of anagrams. This method ensures words with the same letters are grouped together efficiently.

Practice

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

easy

A. Use the length of words as keys to group them

B. Store words in a list without any grouping

C. Group words by their first letter only

D. Use sorted strings as keys to group words with the same letters

Solution

1. Step 1: Understand anagram grouping

   Anagrams have the same letters in different orders, so sorting letters gives a common key.

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 group together.

3. Final Answer:

   Use sorted strings as keys to group words with the same letters -> Option D

4. Quick Check:

   Sorted string key groups anagrams [OK]

Hint: Sort each word to find its anagram group key [OK]

Common Mistakes:

• Grouping by word length only
• Using first letter as key
• Not sorting letters before grouping

2. Which Rust code snippet correctly creates a hash map to group anagrams by sorted keys?

easy

A. let mut map: HashMap = HashMap::new();

B. let map = Vec::new();

C. let mut map: HashMap = HashMap::new();

D. let mut map: HashMap = HashMap::new();

Solution

1. Step 1: Identify correct hash map type

   We need keys as sorted strings and values as vectors of strings to hold grouped anagrams.

2. Step 2: Match Rust syntax for hash map

   HashMap correctly maps sorted keys to lists of words.

3. Final Answer:

   let mut map: HashMap = HashMap::new(); -> Option A

4. Quick Check:

   HashMap with String keys and Vec<String> values [OK]

Hint: Use HashMap for grouping anagrams [OK]

Common Mistakes:

• Using Vec instead of HashMap
• Wrong value type (String instead of Vec<String>)
• Incorrect key type (i32 instead of String)

3. What is the output of this Rust code that groups anagrams?

use std::collections::HashMap;

fn group_anagrams(words: Vec<&str>) -> Vec {
    let mut map: HashMap = HashMap::new();
    for word in words {
        let mut chars: Vec<char> = word.chars().collect();
        chars.sort_unstable();
        let key = chars.into_iter().collect::<String>();
        map.entry(key).or_default().push(word.to_string());
    }
    map.into_values().collect()
}

fn main() {
    let input = vec!["eat", "tea", "tan", "ate", "nat", "bat"];
    let result = group_anagrams(input);
    println!("{:?}", result);
}

medium

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

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

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

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

Solution

1. Step 1: Sort each word to create 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 same sorted key are grouped: ["eat", "tea", "ate"], ["tan", "nat"], ["bat"].

3. Final Answer:

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

4. Quick Check:

   Sorted keys group anagrams [OK]

Hint: Sort letters and group words by sorted key [OK]

Common Mistakes:

• Not sorting letters before grouping
• Grouping single words separately
• Mixing order of groups incorrectly

4. Identify the bug in this Rust code for grouping anagrams:

use std::collections::HashMap;

fn group_anagrams(words: Vec<&str>) -> Vec {
    let mut map: HashMap = HashMap::new();
    for word in words {
        let mut chars: Vec<char> = word.chars().collect();
        chars.sort(); // Bug here
        let key = chars.into_iter().collect::<String>();
        map.entry(key).or_default().push(word.to_string());
    }
    map.into_values().collect()
}

medium

A. Use sort_unstable() instead of sort() for better performance

B. Change chars.into_iter() to chars.iter()

C. Use a HashSet instead of HashMap

D. Convert word to lowercase before sorting

Solution

1. Step 1: Identify sorting method issue

   Using chars.sort() works but sort_unstable() is preferred for primitive types like char for speed.

2. Step 2: Explain why sort_unstable() is better

   sort_unstable() is faster and sufficient here because order stability is not needed for grouping anagrams.

3. Final Answer:

   Use sort_unstable() instead of sort() for better performance -> Option A

4. Quick Check:

   sort_unstable() improves sorting speed [OK]

Hint: Use sort_unstable() for sorting chars in anagrams [OK]

Common Mistakes:

• Using sort() unnecessarily slowing code
• Changing iterator type incorrectly
• Ignoring case sensitivity issues

5. Given a list of words with mixed case and spaces, how would you modify the Rust code to group anagrams correctly ignoring case and spaces? Example input: ["Listen", "Silent", "en list", "in lets"]

hard

A. Sort letters without any changes to words

B. Convert words to lowercase and remove spaces before sorting letters

C. Use word length as key for grouping

D. Group words by their first character only

Solution

1. Step 1: Normalize words by removing spaces and converting to lowercase

   To group anagrams ignoring case and spaces, clean words by removing spaces and making all letters lowercase.

2. Step 2: Sort letters of normalized words and use as keys

   After normalization, sort letters to get keys that group all anagrams regardless of case or spaces.

3. Final Answer:

   Convert words to lowercase and remove spaces before sorting letters -> Option B

4. Quick Check:

   Normalize words before sorting for correct grouping [OK]

Hint: Lowercase and remove spaces before sorting letters [OK]

Common Mistakes:

• Not normalizing case and spaces
• Using length or first letter as key
• Sorting original words without cleaning