Frequency Counter Pattern Using Hash Map in DSA C

Mental Model

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

Analogy: Imagine you have a basket of fruits and you write down how many apples, bananas, and oranges you have on a piece of paper.

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

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3, 2]

Goal: Count how many times each number appears in the array.

Step 1: Add 2 to map with count 1

{2:1}

Why: First time seeing 2, start count at 1

Step 2: Add 3 to map with count 1

{2:1, 3:1}

Why: First time seeing 3, start count at 1

Step 3: Increase count of 2 to 2

{2:2, 3:1}

Why: 2 appeared again, increase count

Step 4: Add 4 to map with count 1

{2:2, 3:1, 4:1}

Why: First time seeing 4, start count at 1

Step 5: Increase count of 3 to 2

{2:2, 3:2, 4:1}

Why: 3 appeared again, increase count

Step 6: Increase count of 2 to 3

{2:3, 3:2, 4:1}

Why: 2 appeared again, increase count

Result:

Final map: {2:3, 3:2, 4:1}

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node for linked list in each bucket
typedef struct Node {
    int key;
    int count;
    struct Node* next;
} Node;

// Simple hash map with chaining
#define SIZE 10

Node* hashMap[SIZE] = {NULL};

// Hash function for integers
int hash(int key) {
    return (key % SIZE + SIZE) % SIZE;
}

// Find node with key in bucket
Node* find(Node* head, int key) {
    while (head != NULL) {
        if (head->key == key) {
            return head;
        }
        head = head->next;
    }
    return NULL;
}

// Insert or update count for key
void insert(int key) {
    int index = hash(key);
    Node* node = find(hashMap[index], key);
    if (node != NULL) {
        node->count++;
    } else {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->key = key;
        newNode->count = 1;
        newNode->next = hashMap[index];
        hashMap[index] = newNode;
    }
}

// Print all keys and counts
void printFrequency() {
    for (int i = 0; i < SIZE; i++) {
        Node* curr = hashMap[i];
        while (curr != NULL) {
            printf("%d: %d\n", curr->key, curr->count);
            curr = curr->next;
        }
    }
}

int main() {
    int arr[] = {2, 3, 2, 4, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < n; i++) {
        insert(arr[i]);
    }

    printFrequency();
    return 0;
}

Node* node = find(hashMap[index], key);

Check if key already exists in the map

if (node != NULL) { node->count++; } else {

If found, increase count; else create new node with count 1

newNode->next = hashMap[index]; hashMap[index] = newNode;

Insert new node at head of bucket list

for (int i = 0; i < n; i++) { insert(arr[i]); }

Process each array element to build frequency map

Output

2: 3

3: 2

4: 1

Complexity Analysis

Time: O(n) because we process each element once and hash map operations are average O(1)

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

vs Alternative: Compared to nested loops counting frequencies (O(n^2)), hash map is much faster

Edge Cases

empty array

No insertions happen, map stays empty, no output

DSA C

for (int i = 0; i < n; i++) {
        insert(arr[i]);
    }

all elements same

One key with count equal to array length

DSA C

if (node != NULL) {
        node->count++;
    } else {

elements with negative numbers

Hash function handles negative keys correctly using modulo adjustment for positive indices

DSA C

int hash(int key) {
    return (key % SIZE + SIZE) % SIZE;
}

When to Use This Pattern

When you need to count how many times items appear quickly, use a frequency counter with a hash map to store counts efficiently.

Common Mistakes

Mistake: Not checking if key already exists before inserting, causing duplicates.
Fix: Always search for key first; if found, increase count instead of inserting new node.

Mistake: Using a poor hash function causing many collisions.
Fix: Use a simple modulo hash for integers and handle collisions with chaining.

Summary

Counts how many times each item appears using a hash map.

Use when you need fast frequency counts of items in a collection.

The key is to check if the item exists and update count or add new entry.

Practice

1. What is the main purpose of using a hash map in the Frequency Counter Pattern?

easy

A. To reverse the order of elements in the collection

B. To sort the elements in ascending order

C. To remove duplicate elements from the collection

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

Solution

1. Step 1: Understand the role of a hash map

   A hash map stores key-value pairs, allowing quick lookup and update of counts.

2. Step 2: Apply to frequency counting

   Using a hash map, we can track how many times each element appears by incrementing counts.

3. Final Answer:

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

4. Quick Check:

   Frequency counting = Counting elements [OK]

Hint: Hash map keys track elements, values track counts [OK]

Common Mistakes:

• Thinking hash map sorts elements
• Confusing frequency counting with removing duplicates
• Using arrays instead of hash maps for counting

2. Which of the following is the correct syntax to declare a hash map in C for counting frequencies of characters?

easy

A. map freq;

B. int freq[256] = {0};

C. unordered_map freq;

D. HashMap freq = new HashMap();

Solution

1. Step 1: Recognize C language limitations

   C does not have built-in hash map types like C++ STL's map or unordered_map.

2. Step 2: Use array for frequency counting in C

   We use an integer array of size 256 (for ASCII chars) initialized to zero to count frequencies.

3. Final Answer:

   int freq[256] = {0}; -> Option B

4. Quick Check:

   C uses arrays for frequency counting [OK]

Hint: In C, use arrays for frequency counts, not map types [OK]

Common Mistakes:

• Using C++ STL syntax in C code
• Trying to declare map or unordered_map in C
• Not initializing frequency array to zero

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

char str[] = "aabbcc";
int freq[256] = {0};
for (int i = 0; str[i] != '\0'; i++) {
    freq[(int)str[i]]++;
}
printf("%d", freq['b']);

medium

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Count occurrences of 'b' in the string

   The string "aabbcc" has two 'b' characters at positions 2 and 3.

2. Step 2: Check frequency array value for 'b'

   freq['b'] is incremented twice, so freq['b'] = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Count of 'b' = 2 [OK]

Hint: Count characters manually, then check freq array [OK]

Common Mistakes:

• Confusing character ASCII codes
• Forgetting null terminator in loop condition
• Printing freq for wrong character

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

char str[] = "hello";
int freq[256];
for (int i = 0; str[i] != '\0'; i++) {
    freq[(int)str[i]]++;
}
printf("%d", freq['l']);

medium

A. freq array is not initialized to zero

B. Loop condition should be i < strlen(str)

C. Casting str[i] to int is incorrect

D. printf format specifier should be %c

Solution

1. Step 1: Check initialization of freq array

   The freq array is declared but not initialized, so it contains garbage values.

2. Step 2: Effect on frequency counting

   Incrementing uninitialized values leads to incorrect counts; freq should be zeroed before use.

3. Final Answer:

   freq array is not initialized to zero -> Option A

4. Quick Check:

   Initialize freq array to zero before counting [OK]

Hint: Always zero frequency array before counting [OK]

Common Mistakes:

• Assuming uninitialized arrays start at zero
• Using wrong printf format for integers
• Misunderstanding loop conditions with null terminator

5. Given two strings s1 = "listen" and s2 = "silent", which approach using frequency counters correctly checks if they are anagrams in C?

hard

A. Count frequencies of characters in both strings using arrays, then compare arrays element-wise

B. Sort both strings and compare them character by character

C. Check if lengths are equal, then check if first characters match

D. Use a hash map to store characters of s1 only and check if s2 contains them

Solution

1. Step 1: Use frequency arrays for both strings

   Create two arrays freq1 and freq2 of size 256, initialize to zero, count characters in s1 and s2 respectively.

2. Step 2: Compare frequency arrays element-wise

   If all counts match for every character, s1 and s2 are anagrams; otherwise, they are not.

3. Final Answer:

   Count frequencies of characters in both strings using arrays, then compare arrays element-wise -> Option A

4. Quick Check:

   Frequency arrays equal means anagrams [OK]

Hint: Compare frequency arrays to confirm anagrams [OK]

Common Mistakes:

• Only counting one string's characters
• Comparing only string lengths or first characters
• Assuming sorting is the only way to check anagrams