Frequency Counter Pattern Using Hash Map in DSA C#

Mental Model

Count how many times each item appears by using a box that remembers counts for each item.

Analogy: Imagine you have a basket of fruits and a notebook. Each time you see a fruit, you write down its name and add one to its count in the notebook.

Basket: [apple, banana, apple, orange, banana]
Notebook:
apple -> 2
banana -> 2
orange -> 1

Dry Run Walkthrough

Input: list: [apple, banana, apple, orange, banana]

Goal: Count how many times each fruit appears in the list.

Step 1: Look at first fruit 'apple', add it to the map with count 1

{apple: 1}

Why: We start counting the first fruit.

Step 2: Look at second fruit 'banana', add it to the map with count 1

{apple: 1, banana: 1}

Why: New fruit found, start its count.

Step 3: Look at third fruit 'apple', increase its count to 2

{apple: 2, banana: 1}

Why: We saw 'apple' again, so add one more.

Step 4: Look at fourth fruit 'orange', add it to the map with count 1

{apple: 2, banana: 1, orange: 1}

Why: New fruit found, start its count.

Step 5: Look at fifth fruit 'banana', increase its count to 2

{apple: 2, banana: 2, orange: 1}

Why: We saw 'banana' again, so add one more.

Result:

{apple: 2, banana: 2, orange: 1}

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class FrequencyCounter
{
    public static Dictionary<string, int> CountFrequencies(string[] items)
    {
        var frequencyMap = new Dictionary<string, int>();
        foreach (var item in items)
        {
            if (frequencyMap.ContainsKey(item))
            {
                frequencyMap[item] += 1; // increase count for existing item
            }
            else
            {
                frequencyMap[item] = 1; // add new item with count 1
            }
        }
        return frequencyMap;
    }

    static void Main()
    {
        string[] fruits = { "apple", "banana", "apple", "orange", "banana" };
        var result = CountFrequencies(fruits);
        foreach (var pair in result)
        {
            Console.WriteLine(pair.Key + ": " + pair.Value);
        }
    }
}

if (frequencyMap.ContainsKey(item))

Check if item already counted to decide increase or add new

frequencyMap[item] += 1; // increase count for existing item

Increase count for item seen before

frequencyMap[item] = 1; // add new item with count 1

Add new item with initial count

Output

apple: 2

banana: 2

orange: 1

Complexity Analysis

Time: O(n) because we look at each item once to count frequencies

Space: O(n) because in worst case all items are unique and stored in the map

vs Alternative: Compared to nested loops counting each item repeatedly (O(n²)), this uses a hash map for fast counting in one pass

Edge Cases

empty list

Returns an empty frequency map with no entries

DSA C#

foreach (var item in items)

all items are the same

Returns a map with one key and count equal to list length

DSA C#

frequencyMap[item] += 1;

all items are unique

Returns a map with each item count as 1

DSA C#

frequencyMap[item] = 1;

When to Use This Pattern

When you need to count how many times things appear in a list or array, use the frequency counter pattern with a hash map for fast counting.

Common Mistakes

Mistake: Forgetting to check if the item already exists in the map before increasing count
Fix: Always check with ContainsKey before incrementing count to avoid errors

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 go, avoiding repeated scanning.

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