Frequency Counter Pattern Using Hash Map in DSA C# - Time & Space Complexity

Time Complexity: Frequency Counter Pattern Using Hash Map

O(n)

Understanding Time Complexity

We want to understand how fast we can count how many times each item appears in a list using a hash map.

The question is: how does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var frequency = new Dictionary<char, int>();
string input = "example";

foreach (char c in input)
{
    if (frequency.ContainsKey(c))
        frequency[c]++;
    else
        frequency[c] = 1;
}
    

This code counts how many times each character appears in the string.

Identify Repeating Operations

• Primary operation: Looping through each character in the string once.
• How many times: Exactly once for each character (n times, where n is string length).
• Inside loop: Checking and updating the hash map, which is very fast (constant time).

How Execution Grows With Input

As the string gets longer, the number of steps grows directly with the number of characters.

Input Size (n)	Approx. Operations
10	About 10 checks and updates
100	About 100 checks and updates
1000	About 1000 checks and updates

Pattern observation: The work grows evenly as the input grows; doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to count frequencies grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Since we check inside a loop, it must be O(n²) because of nested work."

[OK] Correct: The hash map lookup and update happen in constant time, not a loop inside a loop, so it stays O(n).

Interview Connect

Knowing how to count items quickly using a hash map is a key skill. It shows you can use simple tools to solve common problems efficiently.

Self-Check

"What if we used a list instead of a hash map to count frequencies? How would the time complexity change?"

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