Frequency Counter Pattern Using Hash Map in DSA C# - 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↓

Increment element count by 1

↓

Repeat for all elements

↓

Hash map contains frequency of each element

↓

Use frequency data as needed

↓

End

Start with an empty hash map. For each element, check if it exists in the map. If not, add it with count 1; if yes, increase its count. After processing all elements, the map holds frequencies.

Execution Sample

DSA C#

string input = "apple apple banana apple orange banana";
Dictionary<string, int> freq = new Dictionary<string, int>();
foreach (var word in input.Split(' ')) {
  if (freq.ContainsKey(word)) freq[word]++;
  else freq[word] = 1;
}

Counts how many times each word appears in the input string using a hash map.

Execution Table

Step	Operation	Current Word	Hash Map State	Action Taken	Visual State
1	Start	-	{}	Initialize empty hash map	{}
2	Process word	apple	{}	Add 'apple' with count 1	{apple:1}
3	Process word	apple	{apple:1}	Increment 'apple' count to 2	{apple:2}
4	Process word	banana	{apple:2}	Add 'banana' with count 1	{apple:2, banana:1}
5	Process word	apple	{apple:2, banana:1}	Increment 'apple' count to 3	{apple:3, banana:1}
6	Process word	orange	{apple:3, banana:1}	Add 'orange' with count 1	{apple:3, banana:1, orange:1}
7	Process word	banana	{apple:3, banana:1, orange:1}	Increment 'banana' count to 2	{apple:3, banana:2, orange:1}
8	End	-	{apple:3, banana:2, orange:1}	All words processed	{apple:3, banana:2, orange:1}

💡 All words processed, frequency map complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
freq	{}	{apple:1}	{apple:2}	{apple:2, banana:1}	{apple:3, banana:1}	{apple:3, banana:1, orange:1}	{apple:3, banana:2, orange:1}	{apple:3, banana:2, orange:1}
current word	-	apple	apple	banana	apple	orange	banana	-

Key Moments - 3 Insights

Why do we check if the word exists in the hash map before adding or incrementing?

Because if the word is not yet in the map, we must add it with count 1. If we skip this check, trying to increment a non-existing key causes an error. See execution_table steps 2 and 3 where 'apple' is first added then incremented.

What happens if the input is empty?

The loop does not run, so the hash map remains empty as shown in step 1 and step 8. No words processed means no entries.

Why do we split the input string by spaces?

Splitting by spaces breaks the input into individual words to count each separately. Without splitting, the entire string would be treated as one word. This is the basis for the loop in the code sample.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the count of 'apple' after processing?

A 3

B 1

C 2

D 4

💡 Hint

Check the 'Hash Map State' and 'Action Taken' columns at step 5.

At which step does 'banana' first appear in the hash map?

A Step 6

B Step 3

C Step 4

D Step 7

💡 Hint

Look at the 'Current Word' and 'Hash Map State' columns to see when 'banana' is added.

If the input had an extra 'orange' word at the end, how would the final count for 'orange' change?

A It would stay 1

B It would become 2

C It would become 3

D It would be removed

💡 Hint

Refer to how counts increment when a word repeats, as shown for 'apple' and 'banana'.

Concept Snapshot

Frequency Counter Pattern Using Hash Map:
- Start with empty hash map
- For each element, check if it exists
- If not, add with count 1
- If yes, increment count
- Result: hash map with frequencies
- Useful for counting occurrences efficiently

Full Transcript

The Frequency Counter Pattern uses a hash map to count how many times each element appears in a collection. We start with an empty map. For each element, we check if it is already in the map. If not, we add it with count 1. If yes, we increase its count by 1. After processing all elements, the map holds the frequency of each element. This method is efficient and avoids nested loops. The example code counts words in a string by splitting it and updating the map. The execution table shows each step, how the map changes, and the actions taken. Key moments clarify why we check existence before incrementing and what happens with empty input. The visual quiz tests understanding of counts at specific steps and how changes affect the map.

Practice

1. What is the main purpose of using a frequency counter pattern with a hash map in algorithms?

easy

A. To count how many times each element appears in a collection

B. To sort elements in ascending order

C. To reverse the order of elements

D. To find the maximum value in a list

Solution

1. Step 1: Understand frequency counter pattern

   The frequency counter pattern uses a hash map to store counts of each element in a collection.

2. Step 2: Identify the purpose

   This pattern helps to quickly find how many times each element appears, which is useful for comparisons or validations.

3. Final Answer:

   To count how many times each element appears in a collection -> Option A

4. Quick Check:

   Frequency counter = count elements [OK]

Hint: Frequency counter counts occurrences using a hash map [OK]

Common Mistakes:

• Confusing frequency counting with sorting
• Thinking it reverses elements
• Assuming it finds max value

2. Which of the following C# code snippets correctly initializes a frequency counter using a Dictionary for integers?

easy

A. var freq = new HashSet<int>();

B. var freq = new List<int>();

C. var freq = new Dictionary();

D. var freq = new int[10];

Solution

1. Step 1: Identify correct data structure for frequency counting

   A Dictionary maps each integer to its count, perfect for frequency counting.

2. Step 2: Check other options

   List<int> stores values but not counts, HashSet<int> stores unique values without counts, int[] is fixed size and less flexible.

3. Final Answer:

   var freq = new Dictionary(); -> Option C

4. Quick Check:

   Dictionary for frequency map [OK]

Hint: Use Dictionary to map element to count [OK]

Common Mistakes:

• Using List instead of Dictionary for counts
• Using HashSet which stores only unique elements
• Using fixed-size array without mapping keys

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

var arr = new int[] {1, 2, 2, 3, 3, 3};
var freq = new Dictionary();
foreach (var num in arr) {
  if (freq.ContainsKey(num)) freq[num]++;
  else freq[num] = 1;
}
foreach (var kvp in freq) {
  Console.Write(kvp.Key + ":" + kvp.Value + " ");
}

medium

A. 3:3 2:2 1:1

B. 1:1 2:2 3:3

C. 1:1 2:1 3:1

D. 1:3 2:2 3:1

Solution

1. Step 1: Count frequencies in array

   1 appears once, 2 appears twice, 3 appears three times.

2. Step 2: Output order in Dictionary foreach

   Dictionary preserves insertion order in recent C# versions, so output is 1:1 2:2 3:3.

3. Final Answer:

   1:1 2:2 3:3 -> Option B

4. Quick Check:

   Count each element correctly [OK]

Hint: Count each element, print in insertion order [OK]

Common Mistakes:

• Mixing counts of elements
• Assuming Dictionary outputs sorted keys
• Forgetting to increment counts

4. Identify the error in the following C# code that tries to count character frequencies in a string:

string text = "hello";
var freq = new Dictionary();
foreach (char c in text) {
  freq[c] += 1;
}

medium

A. Trying to increment a key that may not exist causes a KeyNotFoundException

B. The dictionary is not initialized

C. The foreach loop syntax is incorrect

D. Characters cannot be used as dictionary keys

Solution

1. Step 1: Analyze dictionary usage

   freq[c] += 1 assumes key c exists, but keys are not added before incrementing.

2. Step 2: Identify exception cause

   Accessing freq[c] when c is not a key throws KeyNotFoundException.

3. Final Answer:

   Trying to increment a key that may not exist causes a KeyNotFoundException -> Option A

4. Quick Check:

   Increment without key check causes error [OK]

Hint: Check key exists before incrementing frequency [OK]

Common Mistakes:

• Assuming keys auto-initialize in Dictionary
• Ignoring exception on missing keys
• Misunderstanding foreach syntax

5. Given two integer arrays arr1 and arr2, which C# code snippet correctly uses the frequency counter pattern to check if arr2 contains the squares of all elements in arr1 with matching frequencies?

hard

A. var freq1 = new Dictionary();
var freq2 = new Dictionary();
foreach(var num in arr1) freq1[num * num] = freq1.GetValueOrDefault(num * num,0) + 1;
foreach(var num in arr2) freq2[num] = freq2.GetValueOrDefault(num,0) + 1;
return freq1.SequenceEqual(freq2);

B. var freq1 = new Dictionary();
foreach(var num in arr1) freq1[num * num] = freq1.GetValueOrDefault(num * num,0) + 1;
foreach(var num in arr2) { if(!freq1.ContainsKey(num)) return false; freq1[num]--; } return freq1.Values.All(v => v == 0);

C. var freq1 = new Dictionary();
var freq2 = new Dictionary();
foreach(var num in arr1) freq1[num] = freq1.GetValueOrDefault(num,0) + 1;
foreach(var num in arr2) freq2[num * num] = freq2.GetValueOrDefault(num * num,0) + 1;
return freq1.SequenceEqual(freq2);

D. var freq1 = new Dictionary();
var freq2 = new Dictionary();
foreach(var num in arr1) freq1[num] = freq1.GetValueOrDefault(num,0) + 1;
foreach(var num in arr2) freq2[num] = freq2.GetValueOrDefault(num,0) + 1;
foreach(var kvp in freq1) { if(!freq2.ContainsKey(kvp.Key * kvp.Key) || freq2[kvp.Key * kvp.Key] != kvp.Value) return false; } return true;

Solution

1. Step 1: Build frequency maps for arr1 and arr2

   freq1 counts elements in arr1, freq2 counts elements in arr2.

2. Step 2: Check if freq2 has squares of freq1 keys with matching counts

   For each key in freq1, check if freq2 contains key squared with same frequency.

3. Final Answer:

   Code snippet C correctly implements the frequency counter pattern for this problem -> Option D

4. Quick Check:

   Compare freq1 keys squared with freq2 frequencies [OK]

Hint: Map arr1 counts, verify squared keys in arr2 counts [OK]

Common Mistakes:

• Comparing frequency dictionaries without squaring keys
• Decrementing counts without checking all keys
• Using SequenceEqual without sorting or matching keys