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

Concept Flow - Frequency Counter Pattern Using Hash Map

Start with empty hash map

↓

Read next element from input

↓

Check if element in hash map?

No→Add element with count=1

↓

Increment count by 1

↓

Repeat for all elements

↓

Hash map now has frequency counts

↓

Use frequency data as needed

↓

End

Start with an empty hash map, read each element, update its count, and finally have frequency counts for all elements.

Execution Sample

DSA C

int arr[] = {2, 3, 2, 4, 3};
int n = 5;
HashMap freq = {};
for (int i = 0; i < n; i++) {
  freq[arr[i]] = (freq[arr[i]] ? freq[arr[i]] : 0) + 1;
}

Counts how many times each number appears in the array using a hash map.

Execution Table

Step	Operation	Element Processed	Hash Map State	Visual State
1	Start	None	{}	{}
2	Process element	2	{2:1}	{2:1}
3	Process element	3	{2:1, 3:1}	{2:1, 3:1}
4	Process element	2	{2:2, 3:1}	{2:2, 3:1}
5	Process element	4	{2:2, 3:1, 4:1}	{2:2, 3:1, 4:1}
6	Process element	3	{2:2, 3:2, 4:1}	{2:2, 3:2, 4:1}
7	End	None	{2:2, 3:2, 4:1}	{2:2, 3:2, 4:1}

💡 All elements processed, frequency counts complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
freq	{}	{2:1}	{2:1, 3:1}	{2:2, 3:1}	{2:2, 3:1, 4:1}	{2:2, 3:2, 4:1}	{2:2, 3:2, 4:1}
element	None	2	3	2	4	3	None

Key Moments - 3 Insights

Why do we add the element with count 1 if it is not in the hash map?

Because the first time we see an element, its count starts at 1. This is shown in execution_table row 2 where element 2 is added with count 1.

Why do we increment the count instead of replacing it?

Because we want to keep track of how many times the element appears. Incrementing updates the count correctly, as seen in execution_table rows 4 and 6 where counts increase.

What happens if the input array is empty?

The hash map remains empty, as no elements are processed. This is like execution_table row 1 where freq is empty at start and no further steps occur.

Visual Quiz - 3 Questions

Look at the execution_table, what is the hash map state after processing the third element?

A {2:2, 3:2}

B {2:2, 3:1}

C {2:1, 3:1}

D {2:1, 3:2}

💡 Hint

Check row 4 in execution_table where the third element (2) is processed.

At which step does the element 4 get added to the hash map?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look at execution_table row 5 where element 4 is processed and added.

If the input array had one more '3' at the end, what would be the final count of 3 in the hash map?

A 4

B 2

C 3

D 1

💡 Hint

Currently count of 3 is 2 at final step (row 7), adding one more increments it by 1.

Concept Snapshot

Frequency Counter Pattern Using Hash Map:
- Start with empty hash map
- For each element, check if in map
- If not, add with count 1
- If yes, increment count
- Result: hash map with element frequencies
- Useful for counting duplicates or comparing data

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 hash map. For each element in the input, we check if it is already in the hash map. If it is not, we add it with a count of 1. If it is already there, we increase its count by 1. After processing all elements, the hash map holds the frequency of each element. This pattern helps quickly count duplicates or compare data sets efficiently.