Frequency Counter Pattern Using Hash Map in DSA Go

Mental Model

Count how many times each item appears by using a map to store counts.

Analogy: Like counting how many apples, oranges, and bananas you have by putting each fruit in separate jars and adding one each time you see that fruit.

items: [a, b, a, c, b]
map: {}

After counting:
map: {a:2, b:2, c:1}

Dry Run Walkthrough

Input: list: [a, b, a, c, b]

Goal: Count how many times each letter appears in the list

Step 1: Add 'a' to map with count 1

map: {a:1}

Why: First time seeing 'a', start count at 1

Step 2: Add 'b' to map with count 1

map: {a:1, b:1}

Why: First time seeing 'b', start count at 1

Step 3: Increment count of 'a' to 2

map: {a:2, b:1}

Why: 'a' seen again, increase count

Step 4: Add 'c' to map with count 1

map: {a:2, b:1, c:1}

Why: First time seeing 'c', start count at 1

Step 5: Increment count of 'b' to 2

map: {a:2, b:2, c:1}

Why: 'b' seen again, increase count

Result:

map: {a:2, b:2, c:1}

Annotated Code

DSA Go

package main

import (
	"fmt"
)

// frequencyCounter counts how many times each string appears in the list
func frequencyCounter(items []string) map[string]int {
	counts := make(map[string]int)
	for _, item := range items {
		counts[item]++ // increase count for this item
	}
	return counts
}

func main() {
	list := []string{"a", "b", "a", "c", "b"}
	result := frequencyCounter(list)
	fmt.Println(result)
}

for _, item := range items {

iterate over each item in the list

counts[item]++ // increase count for this item

increment count for current item in map

Output

map[a:2 b:2 c:1]

Complexity Analysis

Time: O(n) because we look at each item once to count

Space: O(n) because in worst case all items are unique and stored in map

vs Alternative: Using nested loops to count each item would be O(n^2), so hash map is much faster

Edge Cases

empty list

returns empty map with no counts

DSA Go

for _, item := range items {

all items the same

map has one key with count equal to list length

DSA Go

counts[item]++ // increase count for this item

list with unique items

map has all keys with count 1

DSA Go

counts[item]++ // increase count for this item

When to Use This Pattern

When you need to count or compare frequencies of items quickly, use the frequency counter pattern with a hash map to store counts efficiently.

Common Mistakes

Mistake: Forgetting to initialize the count before incrementing, causing zero value confusion.
Fix: Use counts[item]++ which works even if key is not present, as Go initializes missing keys to zero.

Summary

Counts how many times each item appears using a map.

Use when you need to know frequency of elements in a list quickly.

The key is using a map to store counts and incrementing as you go.

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