Frequency Counter Pattern Using Hash Map in DSA Typescript

Mental Model

Count how many times each item appears by storing counts in a map. This helps compare or find duplicates quickly.

Analogy: Imagine counting how many apples, oranges, and bananas you have by writing numbers next to each fruit name on a paper.

items: [a, b, a, c, b]
map: { }
          ↑ start with empty map

Dry Run Walkthrough

Input: array: ['a', 'b', 'a', 'c', 'b']

Goal: Count how many times each letter appears in the array

Step 1: Read first item 'a', add 'a' to map with count 1

map: { 'a': 1 }

Why: First time seeing 'a', so start count at 1

Step 2: Read second item 'b', add 'b' to map with count 1

map: { 'a': 1, 'b': 1 }

Why: First time seeing 'b', so start count at 1

Step 3: Read third item 'a', increase count of 'a' to 2

map: { 'a': 2, 'b': 1 }

Why: 'a' seen before, so add 1 to existing count

Step 4: Read fourth item 'c', add 'c' to map with count 1

map: { 'a': 2, 'b': 1, 'c': 1 }

Why: First time seeing 'c', so start count at 1

Step 5: Read fifth item 'b', increase count of 'b' to 2

map: { 'a': 2, 'b': 2, 'c': 1 }

Why: 'b' seen before, so add 1 to existing count

Result:

map: { 'a': 2, 'b': 2, 'c': 1 }

Annotated Code

DSA Typescript

class FrequencyCounter {
  private map: Record<string, number> = {};

  count(items: string[]): Record<string, number> {
    for (const item of items) {
      if (this.map[item] !== undefined) {
        this.map[item] += 1; // increase count if item exists
      } else {
        this.map[item] = 1; // start count at 1 if new item
      }
    }
    return this.map;
  }
}

const counter = new FrequencyCounter();
const input = ['a', 'b', 'a', 'c', 'b'];
const result = counter.count(input);
console.log(result);

if (this.map[item] !== undefined) {

check if item already counted

this.map[item] += 1; // increase count if item exists

increment count for existing item

this.map[item] = 1; // start count at 1 if new item

initialize count for new item

Output

{"a":2,"b":2,"c":1}

Complexity Analysis

Time: O(n) because we go through all n items once to count

Space: O(k) where k is number of unique items stored in the map

vs Alternative: Without a map, counting would require nested loops O(n^2), which is slower

Edge Cases

empty array

returns empty map {} with no counts

DSA Typescript

for (const item of items) {

array with one item

returns map with that item count 1

DSA Typescript

this.map[item] = 1; // start count at 1 if new item

array with all identical items

returns map with one key and count equal to array length

DSA Typescript

this.map[item] += 1; // increase count if item exists

When to Use This Pattern

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

Common Mistakes

Mistake: Forgetting to initialize count to 1 for new items
Fix: Add else branch to set count to 1 when item not in map

Mistake: Using map[item]++ without checking if item exists, causing undefined + 1 = NaN
Fix: Check if item exists before incrementing, else initialize to 1

Summary

Counts how many times each item appears using a map.

Use when you need to quickly find frequency or duplicates in a list.

The key is to store counts in a map and update as you go.

Practice

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

easy

A. To reverse the order of elements in an array

B. To count how many times each item appears in a collection

C. To remove duplicate items from a list

D. To sort the items in ascending order

Solution

1. Step 1: Understand frequency counting

   The frequency counter pattern counts occurrences of each item in a collection.

2. Step 2: Recognize hash map usage

   A hash map stores each item as a key and its count as the value for quick lookup.

3. Final Answer:

   To count how many times each item appears in a collection -> Option B

4. Quick Check:

   Frequency counter = count items [OK]

Hint: Frequency counter counts occurrences using keys [OK]

Common Mistakes:

• Confusing frequency counting with sorting
• Thinking it removes duplicates instead of counting
• Assuming it reverses arrays

2. Which of the following TypeScript code snippets correctly initializes an empty frequency counter using a hash map?

easy

A. const freq = new Set();

B. const freq = [];

C. const freq: Record = {};

D. const freq = 0;

Solution

1. Step 1: Identify correct hash map initialization

   In TypeScript, an object with string keys and number values is used for frequency counting.

2. Step 2: Check each option

   const freq: Record = {}; uses Record = {} which is correct. Others are array, set, or number, which are incorrect for frequency counting.

3. Final Answer:

   const freq: Record = {}; -> Option C

4. Quick Check:

   Empty object for frequency map [OK]

Hint: Use object or map for frequency counters [OK]

Common Mistakes:

• Using array or set instead of object
• Initializing frequency counter as a number
• Not specifying key-value structure

3. What will be the output of the following TypeScript code?

const arr = ['a', 'b', 'a', 'c', 'b', 'a'];
const freq: Record = {};
for (const char of arr) {
  freq[char] = (freq[char] || 0) + 1;
}
console.log(freq);

medium

A. {"a": 3, "b": 2, "c": 1}

B. {"a": 1, "b": 1, "c": 1}

C. [3, 2, 1]

D. Error: freq is not iterable

Solution

1. Step 1: Loop through array and count frequencies

   Each character's count is incremented in freq. 'a' appears 3 times, 'b' 2 times, 'c' 1 time.

2. Step 2: Output the freq object

   console.log prints the object with counts: {"a": 3, "b": 2, "c": 1}.

3. Final Answer:

   {"a": 3, "b": 2, "c": 1} -> Option A

4. Quick Check:

   Count each char correctly [OK]

Hint: Increment count or start at zero for each key [OK]

Common Mistakes:

• Printing array instead of object
• Not initializing counts to zero
• Trying to iterate freq as array

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

const str = "hello";
const freq: Record = {};
for (let i = 0; i <= str.length; i++) {
  const char = str[i];
  freq[char] = (freq[char] || 0) + 1;
}
console.log(freq);

medium

A. freq should be initialized as an array, not object

B. The code is correct and will run without errors

C. char variable should be declared outside the loop

D. Loop condition should be i < str.length, not i <= str.length

Solution

1. Step 1: Check loop boundary

   The loop runs from i = 0 to i <= str.length, which accesses str[str.length] (undefined).

2. Step 2: Fix loop condition

   Change condition to i < str.length to avoid accessing undefined character.

3. Final Answer:

   Loop condition should be i < str.length, not i <= str.length -> Option D

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Use < length, not <= length in loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing freq as array instead of object
• Declaring variables outside loop unnecessarily

5. Given two arrays of numbers, arr1 and arr2, which TypeScript function correctly uses the frequency counter pattern to check if arr2 contains the squares of all elements in arr1 with the same frequency?

hard

A. function sameFrequency(arr1: number[], arr2: number[]): boolean {
const freq1: Record = {};
const freq2: Record = {};
for (const num of arr1) freq1[num] = (freq1[num] || 0) + 1;
for (const num of arr2) freq2[num] = (freq2[num] || 0) + 1;
for (const key in freq1) {
if (freq2[Number(key) ** 2] !== freq1[key]) return false;
}
return true;
}

B. function sameFrequency(arr1: number[], arr2: number[]): boolean {
const freq1: Record = {};
for (const num of arr1) freq1[num] = (freq1[num] || 0) + 1;
for (const num of arr2) {
if (!freq1[num * num]) return false;
}
return true;
}

C. function sameFrequency(arr1: number[], arr2: number[]): boolean {
return arr1.length === arr2.length;
}

D. function sameFrequency(arr1: number[], arr2: number[]): boolean {
const freq1 = new Map();
for (const num of arr1) freq1.set(num, (freq1.get(num) || 0) + 1);
for (const num of arr2) {
if (!freq1.has(num * num)) return false;
}
return true;
}

Solution

1. Step 1: Build frequency maps for both arrays

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

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

   Loop over freq1 keys, verify freq2 has key squared with equal frequency.

3. Step 3: Return true if all match, else false

   If any mismatch found, return false; otherwise, return true.

4. Final Answer:

   Function in Option A correctly implements frequency counter for squares check -> Option A

5. Quick Check:

   Compare frequencies of numbers and their squares [OK]

Hint: Count frequencies, compare keys squared with same counts [OK]

Common Mistakes:

• Not comparing frequencies, only presence
• Checking squares incorrectly (num * num vs key squared)
• Ignoring frequency counts in second array