Group Anagrams Using Hash Map in DSA Go - Execution Trace

Concept Flow - Group Anagrams Using Hash Map

Start with list of words

↓

For each word:

↓

Sort letters in word

↓

Use sorted word as key in hash map

↓

Add original word to hash map[key

↓

Repeat for all words

↓

Collect all hash map values as groups

↓

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 Go

words := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
result := groupAnagrams(words)
fmt.Println(result)

Groups words that are anagrams into lists using a hash map keyed by sorted letters.

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"]]	Groups: eat, tea, ate | tan, nat | bat
8	Return result	-	-	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	Final grouped anagrams

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

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
words	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]
current_word	nil	eat	tea	tan	ate	nat	bat	nil
sorted_key	nil	aet	aet	ant	aet	ant	abt	nil
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 letters of each word before using it as a key?

Sorting letters creates a unique key for all anagrams. For example, 'eat', 'tea', and 'ate' all become 'aet'. This groups them together in the hash map as shown in steps 1, 2, and 4 in the execution_table.

What happens if a word's sorted key is not yet in the hash map?

We create a new entry with that key and start a list with the current word. For example, at step 3, 'tan' sorted to 'ant' is not in the map, so a new list is created.

How do we get the final groups of anagrams from the hash map?

After processing all words, we collect all the lists (values) from the hash map. This is shown in step 7 where the groups are collected and returned.

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": ["eat", "tea"], "ant": ["tan", "ate"]}

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

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

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

💡 Hint

Check the 'Hash Map State' column at step 4 in the execution_table.

At which step does the hash map first get a new key 'abt'?

A Step 3

B Step 6

C Step 5

D Step 2

💡 Hint

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

If the word 'bat' was added 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": ["tan"]}

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

💡 Hint

Consider the sorted keys of 'bat' and 'tan' and when they are processed in the execution_table.

Concept Snapshot

Group Anagrams Using Hash Map:
- For each word, sort its letters to create a key.
- Use this key in a hash map to group words.
- Words with same sorted key are anagrams.
- Collect all groups from the hash map values.
- Efficiently groups anagrams in O(N*KlogK) time (N=words, K=word length).

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 letters, 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 hash map. After all words are processed, we collect all lists from the hash map as groups of anagrams. The execution table shows each step with the current word, its sorted key, and the hash map state. The variable tracker shows how variables change after each word is processed. Key moments clarify why sorting is used, what happens when a new key is found, and how final groups are collected. The visual quiz tests understanding of hash map states at different steps. This method efficiently groups anagrams by leveraging sorted keys as hash map keys.

Practice

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

easy

A. Use the last letter of each word as the key

B. Use the length of words as keys to group anagrams

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

D. Use the first letter of each word as the key

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders.

2. Step 2: Use sorted string as key

   Sorting letters of each word gives a unique key for all its anagrams.

3. Final Answer:

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

4. Quick Check:

   Sorted string key = group anagrams [OK]

Hint: Sort letters to find anagram groups quickly [OK]

Common Mistakes:

• Using word length as key misses different anagrams
• Using first or last letter groups unrelated words
• Not sorting letters before using as key

2. Which Go code snippet correctly initializes a hash map to group anagrams?

easy

A. groups := make(map[string][]string)

B. groups := map[string]string{}

C. groups := make([]string, 0)

D. groups := map[int][]string{}

Solution

1. Step 1: Identify map key and value types

   Key should be string (sorted word), value should be slice of strings (anagrams).

2. Step 2: Check Go map initialization syntax

   make(map[string][]string) creates a map with string keys and string slice values.

3. Final Answer:

   groups := make(map[string][]string) -> Option A

4. Quick Check:

   Correct map type and initialization [OK]

Hint: Use map[string][]string for grouping anagrams [OK]

Common Mistakes:

• Using map[string]string instead of map[string][]string
• Using slice instead of map
• Using wrong key or value types

3. What is the output of the following Go code?

package main
import (
  "fmt"
  "sort"
  "strings"
)
func groupAnagrams(strs []string) map[string][]string {
  groups := make(map[string][]string)
  for _, word := range strs {
    letters := strings.Split(word, "")
    sort.Strings(letters)
    key := strings.Join(letters, "")
    groups[key] = append(groups[key], word)
  }
  return groups
}
func main() {
  input := []string{"bat", "tab", "eat", "tea"}
  result := groupAnagrams(input)
  fmt.Println(result)
}

medium

A. map[bat:[bat] tab:[tab] eat:[eat] tea:[tea]]

B. map[abt:[bat] tab:[tab] aet:[eat] tea:[tea]]

C. map[bat:[bat tab] eat:[eat tea]]

D. map[abt:[bat tab] aet:[eat tea]]

Solution

1. Step 1: Sort letters of each word

   "bat" and "tab" sorted to "abt"; "eat" and "tea" sorted to "aet".

2. Step 2: Group words by sorted key

   Words with key "abt" grouped as ["bat", "tab"], with key "aet" grouped as ["eat", "tea"].

3. Final Answer:

   map[abt:[bat tab] aet:[eat tea]] -> Option D

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

Hint: Sorted keys map to anagram groups [OK]

Common Mistakes:

• Not sorting letters before grouping
• Using original words as keys
• Incorrect map output format

4. Find the error in this Go code for grouping anagrams:

func groupAnagrams(strs []string) map[string][]string {
  groups := make(map[string][]string)
  for _, word := range strs {
    letters := strings.Split(word, "")
    sort.Strings(letters)
    key := letters[0]
    groups[key] = append(groups[key], word)
  }
  return groups
}

medium

A. Appending word to wrong map key

B. Using letters[0] as key instead of full sorted string

C. Not initializing the map before use

D. Missing import for strings package

Solution

1. Step 1: Check key creation logic

   Key is set as letters[0], only first letter of sorted word, not full sorted string.

2. Step 2: Understand impact on grouping

   Using only first letter groups unrelated words, failing to group anagrams correctly.

3. Final Answer:

   Using letters[0] as key instead of full sorted string -> Option B

4. Quick Check:

   Full sorted string needed as key [OK]

Hint: Use full sorted string as key, not just first letter [OK]

Common Mistakes:

• Using partial key instead of full sorted string
• Forgetting to join letters into string key
• Not sorting letters before key creation

5. Given the input list ["listen", "silent", "enlist", "google", "gogole", "abc"], which Go code snippet correctly returns the grouped anagrams as a slice of slices of strings (ignoring order)?

hard

A. func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, word := range strs {
letters := strings.Split(word, "")
sort.Strings(letters)
key := strings.Join(letters, "")
groups[key] = append(groups[key], word)
}
result := [][]string{}
for _, group := range groups {
result = append(result, group)
}
return result
}

B. func groupAnagrams(strs []string) [][]string {
groups := make(map[int][]string)
for _, word := range strs {
key := len(word)
groups[key] = append(groups[key], word)
}
result := [][]string{}
for _, group := range groups {
result = append(result, group)
}
return result
}

C. func groupAnagrams(strs []string) [][]string {
groups := make(map[string]string)
for _, word := range strs {
letters := strings.Split(word, "")
sort.Strings(letters)
key := strings.Join(letters, "")
groups[key] = word
}
result := [][]string{}
for _, group := range groups {
result = append(result, []string{group})
}
return result
}

D. func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, word := range strs {
key := word
groups[key] = append(groups[key], word)
}
result := [][]string{}
for _, group := range groups {
result = append(result, group)
}
return result
}

Solution

1. Step 1: Use sorted string as key and map to slice of strings

   func groupAnagrams(strs []string) [][]string { groups := make(map[string][]string) for _, word := range strs { letters := strings.Split(word, "") sort.Strings(letters) key := strings.Join(letters, "") groups[key] = append(groups[key], word) } result := [][]string{} for _, group := range groups { result = append(result, group) } return result } correctly sorts letters, joins them as key, and appends words to groups[key].

2. Step 2: Convert map values to slice of slices

   func groupAnagrams(strs []string) [][]string { groups := make(map[string][]string) for _, word := range strs { letters := strings.Split(word, "") sort.Strings(letters) key := strings.Join(letters, "") groups[key] = append(groups[key], word) } result := [][]string{} for _, group := range groups { result = append(result, group) } return result } collects all groups into a slice of slices and returns it.

3. Final Answer:

   Option A code correctly groups anagrams and returns slice of slices -> Option A

4. Quick Check:

   Sorted key + map to slices + collect groups = correct [OK]

Hint: Sort letters, map to slices, then collect groups [OK]

Common Mistakes:

• Using word length as key groups wrong words
• Using map[string]string loses multiple anagrams per key
• Using original word as key misses grouping