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.

Practice

1. What does the frequency counter pattern using a hash map help you do in a list of items?

easy

A. Count how many times each item appears

B. Sort the list in ascending order

C. Remove duplicate items from the list

D. Find the largest item in the list

Solution

1. Step 1: Understand frequency counting

   The frequency counter pattern counts occurrences of each item in a list using a hash map (dictionary).

2. Step 2: Compare options

   Only Count how many times each item appears describes counting occurrences. Sorting, removing duplicates, or finding largest are different tasks.

3. Final Answer:

   Count how many times each item appears -> Option A

4. Quick Check:

   Frequency counter = count occurrences [OK]

Hint: Frequency counter counts items, not sorts or removes [OK]

Common Mistakes:

• Confusing frequency counting with sorting
• Thinking it removes duplicates automatically
• Assuming it finds max/min values

2. Which of the following is the correct way to create an empty frequency counter using a hash map in Python?

easy

A. freq = []

B. freq = {}

C. freq = ()

D. freq = set()

Solution

1. Step 1: Identify data structure for frequency counter

   A frequency counter uses a hash map, which in Python is a dictionary, created with curly braces {}.

2. Step 2: Check options

   freq = {} uses {}, which creates an empty dictionary. Others create list, tuple, or set, which are incorrect here.

3. Final Answer:

   freq = {} -> Option B

4. Quick Check:

   Empty dict = {} for frequency counter [OK]

Hint: Use {} to create empty dictionary for frequency counter [OK]

Common Mistakes:

• Using [] which creates a list, not a dictionary
• Using () which creates a tuple
• Using set() which creates a set, not a dict

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

def freq_counter(lst):
    freq = {}
    for item in lst:
        freq[item] = freq.get(item, 0) + 1
    return freq

print(freq_counter(['a', 'b', 'a', 'c', 'b', 'a']))

medium

A. {'a': 3, 'b': 2, 'c': 1}

B. {'a': 1, 'b': 1, 'c': 1}

C. {'a': 2, 'b': 2, 'c': 2}

D. Error: KeyError

Solution

1. Step 1: Count each item in the list

   Loop goes through ['a', 'b', 'a', 'c', 'b', 'a']. 'a' appears 3 times, 'b' 2 times, 'c' 1 time.

2. Step 2: Use freq.get(item, 0) + 1 to update counts

   freq.get(item, 0) returns current count or 0 if not found, then adds 1.

3. Final Answer:

   {'a': 3, 'b': 2, 'c': 1} -> Option A

4. Quick Check:

   Count 'a'=3, 'b'=2, 'c'=1 [OK]

Hint: Use dict.get(key,0)+1 to count frequencies safely [OK]

Common Mistakes:

• Forgetting to add 1 to count
• Using freq[item] without get causing KeyError
• Miscounting occurrences

4. Find the error in this frequency counter code and choose the fix:

def freq_counter(lst):
    freq = {}
    for item in lst:
        if item in freq:
            freq[item] += 1
        else:
            freq[item] = 0
    return freq

print(freq_counter(['x', 'y', 'x']))

medium

A. Initialize freq as a list instead of dict

B. Remove the if-else and use freq[item] += 1

C. No error, code works fine

D. Change freq[item] = 0 to freq[item] = 1

Solution

1. Step 1: Identify initialization error

   When item is new, freq[item] is set to 0, but it should start at 1 because we found it once.

2. Step 2: Fix initialization

   Change freq[item] = 0 to freq[item] = 1 to count first occurrence correctly.

3. Final Answer:

   Change freq[item] = 0 to freq[item] = 1 -> Option D

4. Quick Check:

   First occurrence count must be 1 [OK]

Hint: First time count must be 1, not 0 [OK]

Common Mistakes:

• Setting initial count to 0 instead of 1
• Using list instead of dict for frequency
• Ignoring the else block

5. Given two lists of integers, write a function using frequency counter pattern to check if the second list contains the same frequency of elements as the first list.
What will be the output of this code?

def same_frequency(lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    freq1 = {}
    freq2 = {}
    for num in lst1:
        freq1[num] = freq1.get(num, 0) + 1
    for num in lst2:
        freq2[num] = freq2.get(num, 0) + 1
    return freq1 == freq2

print(same_frequency([1,2,2,3], [2,1,3,2]))
print(same_frequency([1,2,2,3], [2,1,3,3]))

hard

A. False\nFalse

B. False\nTrue

C. True\nFalse

D. True\nTrue

Solution

1. Step 1: Build frequency dictionaries for both lists

   freq1 counts {1:1, 2:2, 3:1}, freq2 for first call counts {2:2, 1:1, 3:1} which matches freq1.

2. Step 2: Compare frequency dictionaries

   For second call, freq2 counts {2:1, 1:1, 3:2} which differs from freq1, so returns False.

3. Final Answer:

   True False -> Option C

4. Quick Check:

   Same frequency = True, different frequency = False [OK]

Hint: Compare frequency dicts to check equal element counts [OK]

Common Mistakes:

• Only comparing lengths, not frequencies
• Not building frequency for both lists
• Returning True when frequencies differ