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.