Frequency Counter Pattern Using Hash Map in DSA Go - Execution Trace

Concept Flow - Frequency Counter Pattern Using Hash Map

Start with empty hash map

↓

Iterate over each element in input

↓

Check if element in hash map?

No→Add element with count 1

↓

Increment count by 1

↓

Move to next element

↓

End iteration

↓

Hash map contains frequency counts

↓

Done

We start with an empty hash map, then for each element in the input, we check if it exists in the map. If not, add it with count 1; if yes, increment its count. After processing all elements, the map holds frequency counts.

Execution Sample

DSA Go

package main

import "fmt"

func main() {
    input := []string{"apple", "banana", "apple", "orange", "banana", "apple"}
    freq := make(map[string]int)
    for _, item := range input {
        freq[item]++
    }
    fmt.Println(freq)
}

This code counts how many times each fruit appears in the input slice using a hash map.

Execution Table

Step	Operation	Current Element	Hash Map State	Visual State
1	Start	-	{}	{}
2	Process element	apple	{"apple": 1}	{"apple":1}
3	Process element	banana	{"apple": 1, "banana": 1}	{"apple":1, "banana":1}
4	Process element	apple	{"apple": 2, "banana": 1}	{"apple":2, "banana":1}
5	Process element	orange	{"apple": 2, "banana": 1, "orange": 1}	{"apple":2, "banana":1, "orange":1}
6	Process element	banana	{"apple": 2, "banana": 2, "orange": 1}	{"apple":2, "banana":2, "orange":1}
7	Process element	apple	{"apple": 3, "banana": 2, "orange": 1}	{"apple":3, "banana":2, "orange":1}
8	End iteration	-	{"apple": 3, "banana": 2, "orange": 1}	{"apple":3, "banana":2, "orange":1}

💡 All elements processed, frequency counts complete.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
freq	{}	{"apple":1}	{"apple":1, "banana":1}	{"apple":2, "banana":1}	{"apple":2, "banana":1, "orange":1}	{"apple":2, "banana":2, "orange":1}	{"apple":3, "banana":2, "orange":1}	{"apple":3, "banana":2, "orange":1}
current element	-	apple	banana	apple	orange	banana	apple	-

Key Moments - 3 Insights

Why do we check if the element exists in the hash map before incrementing?

In Go, using freq[item]++ automatically initializes the count to zero if the key doesn't exist, so explicit checking is not needed. This is shown in execution_table rows 2 and 3 where 'apple' and 'banana' are added with count 1 directly.

What happens if the input slice is empty?

The loop does not run, so the hash map remains empty as shown in execution_table step 1, and the final frequency map is {}.

Why does the frequency count increase correctly for repeated elements?

Each time an element repeats, freq[item]++ increments the existing count by 1, as seen in execution_table rows 4, 6, and 7 where counts for 'apple' and 'banana' increase.

Visual Quiz - 3 Questions

Look at the execution_table, what is the frequency count of 'banana' after step 5?

A 0

B 1

C 2

D 3

💡 Hint

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

At which step does the frequency count of 'apple' become 3?

A Step 7

B Step 4

C Step 6

D Step 8

💡 Hint

Look at the 'Hash Map State' column for 'apple' count in execution_table rows.

If the input slice had one more 'orange' at the end, how would the final frequency count for 'orange' change?

A It would become 3

B It would stay 1

C It would become 2

D It would be 0

💡 Hint

Frequency increments by 1 for each occurrence, see variable_tracker for how counts change.

Concept Snapshot

Frequency Counter Pattern Using Hash Map:
- Use a hash map to count occurrences of elements.
- For each element, increment its count in the map.
- If element not present, Go initializes count to 0 automatically.
- After processing, map holds frequency counts.
- Useful for quick frequency lookups and comparisons.

Full Transcript

The Frequency Counter Pattern uses a hash map to count how many times each element appears in a collection. We start with an empty map. For each element in the input, we increase its count in the map. In Go, the map returns zero for missing keys, so incrementing works without explicit checks. After processing all elements, the map contains the frequency of each element. This pattern is efficient and simple for counting occurrences.

Practice

1. What is the main purpose of using a hash map in the Frequency Counter Pattern?

easy

A. To count how many times each item appears in a collection

B. To sort the items in ascending order

C. To remove duplicate items from the collection

D. To reverse the order of items in the collection

Solution

1. Step 1: Understand the role of a hash map

   A hash map stores key-value pairs, allowing quick lookup and update of counts.

2. Step 2: Apply to Frequency Counter Pattern

   We use the hash map to keep track of how many times each item appears by incrementing counts.

3. Final Answer:

   To count how many times each item appears in a collection -> Option A

4. Quick Check:

   Frequency counting = counting items [OK]

Hint: Hash map keys track items, values track counts [OK]

Common Mistakes:

• Thinking hash map sorts items
• Confusing frequency counting with removing duplicates
• Assuming hash map reverses order

2. Which of the following Go code snippets correctly initializes an empty hash map to count frequencies of strings?

easy

A. freq := map[int]string{}

B. freq := make(map[string]int)

C. freq := []string{}

D. freq := make([]int, 0)

Solution

1. Step 1: Identify correct map initialization syntax

   In Go, make(map[string]int) creates a map with string keys and int values.

2. Step 2: Check other options

   freq := map[int]string{} reverses key-value types, C and D create slices, not maps.

3. Final Answer:

   freq := make(map[string]int) -> Option B

4. Quick Check:

   Correct map syntax = make(map[string]int) [OK]

Hint: Use make(map[keyType]valueType) for maps [OK]

Common Mistakes:

• Using slices instead of maps
• Swapping key and value types
• Forgetting to use make() for map initialization

3. What will be the output of the following Go code?

package main
import "fmt"
func main() {
  words := []string{"apple", "banana", "apple", "orange", "banana", "apple"}
  freq := make(map[string]int)
  for _, w := range words {
    freq[w]++
  }
  fmt.Println(freq["apple"])
}

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Count occurrences of "apple" in the slice

   "apple" appears at indices 0, 2, and 5, total 3 times.

2. Step 2: Check frequency map update and print

   freq[w]++ increments count for each word; freq["apple"] is 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Count of "apple" = 3 [OK]

Hint: Count each occurrence, then print frequency [OK]

Common Mistakes:

• Counting unique words instead of occurrences
• Off-by-one errors in counting
• Printing wrong key frequency

4. Identify the error in the following Go code that tries to count frequencies of integers:

package main
import "fmt"
func main() {
  nums := []int{1, 2, 2, 3, 1}
  freq := make(map[int]int)
  for i := 0; i <= len(nums); i++ {
    freq[nums[i]]++
  }
  fmt.Println(freq)
}

medium

A. Loop condition should be i < len(nums), not i <= len(nums)

B. Map initialization is incorrect

C. Frequency increment syntax is wrong

D. Slice nums is empty

Solution

1. Step 1: Check loop boundary conditions

   Loop uses i <= len(nums), which causes index out of range error because last index is len(nums)-1.

2. Step 2: Correct loop condition

   Change to i < len(nums) to avoid accessing invalid index.

3. Final Answer:

   Loop condition should be i < len(nums), not i <= len(nums) -> Option A

4. Quick Check:

   Index out of range fixed by i < len(nums) [OK]

Hint: Use i < len(slice) to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loops
• Misinitializing the map
• Incorrect frequency increment syntax

5. Given two slices of integers, a and b, which Go code snippet correctly checks if b contains the same frequency of elements as a using the Frequency Counter Pattern?

hard

A. freqA := make(map[int]int)
freqB := make(map[int]int)
for _, v := range a {
freqA[v]++
}
for _, v := range b {
freqB[v]++
}
for k, v := range freqA {
if freqB[k] != v {
fmt.Println(false)
return
}
}
fmt.Println(true)

B. freq := make(map[int]int)
for _, v := range a {
freq[v] = 1
}
for _, v := range b {
if freq[v] == 0 {
fmt.Println(false)
return
}
}
fmt.Println(true)

C. freq := make(map[int]int)
for i := 0; i < len(a); i++ {
freq[a[i]]++
freq[b[i]]++
}
for _, count := range freq {
if count%2 != 0 {
fmt.Println(false)
return
}
}
fmt.Println(true)

D. freq := make(map[int]int)
for _, v := range a {
freq[v]++
}
for _, v := range b {
freq[v]--
}
for _, count := range freq {
if count != 0 {
fmt.Println(false)
return
}
}
fmt.Println(true)

Solution

1. Step 1: Build frequency map for a

   Increment counts for each element in a.

2. Step 2: Decrement frequency map for b

   Decrement counts for each element in b.

3. Step 3: Check if all counts are zero

   If any count is not zero, frequencies differ; otherwise, they match.

4. Final Answer:

   freq := make(map[int]int) for _, v := range a { freq[v]++ } for _, v := range b { freq[v]-- } for _, count := range freq { if count != 0 { fmt.Println(false) return } } fmt.Println(true) -> Option D

5. Quick Check:

   Increment a, decrement b, check zero counts [OK]

Hint: Increment for a, decrement for b, then check zeros [OK]

Common Mistakes:

• Only checking presence, not frequency
• Using separate maps without comparing properly
• Assuming counts add up without balancing increments and decrements