Frequency Counter Pattern Using Hash Map in DSA Python

Mental Model

Count how many times each item appears by using a special box that remembers counts.

Analogy: Imagine sorting colored beads into jars where each jar holds beads of one color and you count how many beads go into each jar.

items: [a, b, a, c, b, a]
frequency_map:
  a -> 3
  b -> 2
  c -> 1

Dry Run Walkthrough

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

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

Step 1: Start with empty frequency map

frequency_map: {}

Why: We need a place to store counts for each item

Step 2: See 'a', add 'a' with count 1

frequency_map: {'a': 1}

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

Step 3: See 'b', add 'b' with count 1

frequency_map: {'a': 1, 'b': 1}

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

Step 4: See 'a' again, increase 'a' count to 2

frequency_map: {'a': 2, 'b': 1}

Why: Increment count because 'a' appeared again

Step 5: See 'c', add 'c' with count 1

frequency_map: {'a': 2, 'b': 1, 'c': 1}

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

Step 6: See 'b' again, increase 'b' count to 2

frequency_map: {'a': 2, 'b': 2, 'c': 1}

Why: Increment count because 'b' appeared again

Step 7: See 'a' again, increase 'a' count to 3

frequency_map: {'a': 3, 'b': 2, 'c': 1}

Why: Increment count because 'a' appeared again

Result:

frequency_map: {'a': 3, 'b': 2, 'c': 1}

Annotated Code

DSA Python

class FrequencyCounter:
    def __init__(self):
        self.freq_map = {}

    def count_frequencies(self, items):
        for item in items:
            if item in self.freq_map:
                self.freq_map[item] += 1  # increase count for existing item
            else:
                self.freq_map[item] = 1   # first time seeing this item
        return self.freq_map


if __name__ == '__main__':
    items = ['a', 'b', 'a', 'c', 'b', 'a']
    counter = FrequencyCounter()
    result = counter.count_frequencies(items)
    for key in sorted(result):
        print(f"{key}: {result[key]}")

for item in items:

iterate over each item to process all elements

if item in self.freq_map:

check if item already counted to update count

self.freq_map[item] += 1 # increase count for existing item

increment count for repeated item

self.freq_map[item] = 1 # first time seeing this item

initialize count for new item

Output

a: 3

b: 2

c: 1

Complexity Analysis

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

Space: O(k) where k is number of unique items stored in the frequency map

vs Alternative: Compared to nested loops counting each item separately (O(n^2)), this uses a hash map for O(n) time

Edge Cases

empty list

returns empty frequency map with no errors

DSA Python

for item in items:

list with one item repeated many times

returns frequency map with one key and count equal to list length

DSA Python

self.freq_map[item] += 1  # increase count for existing item

list with all unique items

returns frequency map with each item count as 1

DSA Python

self.freq_map[item] = 1   # first time seeing this item

When to Use This Pattern

When you need to count how many times things appear in a list or string, use the frequency counter pattern with a hash map to track counts efficiently.

Common Mistakes

Mistake: Forgetting to initialize count to 1 for new items
Fix: Add else branch to set count to 1 when item is first seen

Mistake: Using nested loops to count frequencies causing slow performance
Fix: Use a hash map to count in one pass for better efficiency

Summary

Counts how many times each item appears using a hash map.

Use it when you need quick frequency counts of elements in a collection.

The key insight is to store counts as you see items instead of recounting repeatedly.