Why Frequency Counter Pattern Using Hash Map in DSA Go?

The Big Idea

What if you could count thousands of items instantly without mistakes?

The Scenario

Imagine you have a big box of colored marbles and you want to know how many marbles of each color you have. Counting each color one by one by searching through the box every time would take forever!

The Problem

Manually counting each color means you keep looking through the whole box again and again. This is slow and easy to make mistakes, like counting the same marble twice or missing some.

The Solution

The frequency counter pattern uses a hash map to keep track of counts as you look at each marble once. This way, you quickly update counts without searching again and again.

Before vs After

✗ Before

var colors = []string{"red", "blue", "red", "green"}
for _, color := range colors {
    count := 0
    for _, c := range colors {
        if c == color {
            count++
        }
    }
    fmt.Println(color, count)
}

✓ After

var colors = []string{"red", "blue", "red", "green"}
frequency := make(map[string]int)
for _, color := range colors {
    frequency[color]++
}
for color, count := range frequency {
    fmt.Println(color, count)
}

What It Enables

This pattern lets you count items quickly and easily, even in very large collections, making your programs faster and simpler.

Real Life Example

Counting how many times each word appears in a book to find the most common words is a perfect example of using frequency counters.

Key Takeaways

Manually counting is slow and error-prone.

Frequency counters use hash maps to count in one pass.

This makes counting fast and easy for large data.

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