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

Concept Flow - Frequency Counter Pattern Using Hash Map

Start with empty hash map

↓

For each element in input

↓

Check if element in hash map?

No→Add element with count 1

Yes↓

Increase element count by 1

↓

Repeat for all elements

↓

Hash map contains frequency of each element

We start with an empty hash map and go through each element. If the element is new, add it with count 1. If it exists, increase its count. At the end, the map shows how many times each element appears.

Execution Sample

DSA Python

def frequency_counter(arr):
    freq = {}
    for val in arr:
        freq[val] = freq.get(val, 0) + 1
    return freq

This code counts how many times each value appears in the list and stores it in a hash map.

Execution Table

Step	Operation	Current Element	Hash Map State	Action	Visual State
1	Initialize	-	{}	Create empty hash map	{}
2	Process element	3	{}	Add 3 with count 1	{"3": 1}
3	Process element	5	{"3": 1}	Add 5 with count 1	{"3": 1, "5": 1}
4	Process element	3	{"3": 1, "5": 1}	Increase count of 3 to 2	{"3": 2, "5": 1}
5	Process element	2	{"3": 2, "5": 1}	Add 2 with count 1	{"3": 2, "5": 1, "2": 1}
6	Process element	5	{"3": 2, "5": 1, "2": 1}	Increase count of 5 to 2	{"3": 2, "5": 2, "2": 1}
7	Process element	5	{"3": 2, "5": 2, "2": 1}	Increase count of 5 to 3	{"3": 2, "5": 3, "2": 1}
8	Process element	3	{"3": 2, "5": 3, "2": 1}	Increase count of 3 to 3	{"3": 3, "5": 3, "2": 1}
9	End	-	{"3": 3, "5": 3, "2": 1}	All elements processed	{"3": 3, "5": 3, "2": 1}

💡 All elements in the input list have been processed, frequency counts are complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
freq	{}	{"3": 1}	{"3": 1, "5": 1}	{"3": 2, "5": 1}	{"3": 2, "5": 1, "2": 1}	{"3": 2, "5": 2, "2": 1}	{"3": 2, "5": 3, "2": 1}	{"3": 3, "5": 3, "2": 1}	{"3": 3, "5": 3, "2": 1}
val	-	3	5	3	2	5	5	3	-

Key Moments - 3 Insights

Why do we check if the element is already in the hash map before adding?

Because if the element is already there, we need to increase its count instead of adding a new entry. This is shown in steps 4, 6, 7, and 8 where counts increase.

What happens if the input list is empty?

The hash map stays empty as no elements are processed. The code initializes freq as empty and returns it immediately, as no steps beyond initialization occur.

Why do we use freq.get(val, 0) + 1 instead of just freq[val] + 1?

Because freq.get(val, 0) returns 0 if val is not yet in the map, avoiding errors. This allows adding new elements with count 1 smoothly, as seen in steps 2, 3, and 5.

Visual Quiz - 3 Questions

Look at the execution table, what is the hash map state after processing the 5th element?

A {"3": 3, "5": 1, "2": 1}

B {"3": 2, "5": 1, "2": 1}

C {"3": 2, "5": 2, "2": 1}

D {"3": 1, "5": 1, "2": 1}

💡 Hint

Check row 5 in the execution table under 'Visual State' column.

At which step does the count of element '3' become 3?

A Step 4

B Step 6

C Step 8

D Step 7

💡 Hint

Look at the 'Action' and 'Hash Map State' columns for element '3' increments.

If the input list had no repeated elements, how would the hash map counts look?

A All counts would be 1

B All counts would be 0

C Counts would increase for some elements

D Hash map would be empty

💡 Hint

Refer to the logic in the code and how counts increase only when elements repeat.

Concept Snapshot

Frequency Counter Pattern Using Hash Map:
- Use a hash map (dictionary) to count occurrences.
- For each element: if new, add with count 1; if existing, increase count.
- Use freq.get(val, 0) + 1 to handle new keys safely.
- Result: hash map with element frequencies.
- Useful for quick frequency checks and comparisons.

Full Transcript

The Frequency Counter Pattern uses a hash map to count how many times each element appears in a list. We start with an empty map. For each element, if it is not in the map, we add it with count 1. If it is already there, we increase its count by 1. This way, after processing all elements, the map shows the frequency of each element. The code uses freq.get(val, 0) + 1 to safely add or update counts without errors. This pattern is helpful to quickly find how many times each item appears.

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