Frequency Counter Pattern Using Hash Map in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Frequency Counter Pattern in data structures?

It is a technique to count how many times each item appears in a collection, usually using a hash map (object or dictionary) to store counts.

beginner

Why use a hash map for frequency counting?

Because hash maps provide fast lookup, insertion, and update of counts, making frequency counting efficient.

intermediate

TypeScript code snippet: How to initialize a frequency counter for an array of strings?

const freqCounter: Record<string, number> = {};
for (const item of array) {
  freqCounter[item] = (freqCounter[item] || 0) + 1;
}

intermediate

What is the time complexity of counting frequencies using a hash map?

It is O(n), where n is the number of items, because each item is processed once with constant time operations.

intermediate

How does the Frequency Counter Pattern help in comparing two arrays for the same frequency of elements?

By counting frequencies of both arrays and then comparing the counts, we can check if they have the same elements with the same frequency efficiently.

What data structure is commonly used in the Frequency Counter Pattern?

A Hash Map

B Linked List

C Stack

D Queue

Hash maps allow fast counting and lookup of frequencies.

What is the main advantage of using a frequency counter over nested loops for counting elements?

A Works only for numbers

B Uses less memory

C Faster time complexity

D Simpler code but slower

Frequency counters reduce time complexity from O(n²) to O(n).

In TypeScript, how do you update the count of an item in a frequency counter object?

A freqCounter[item] = (freqCounter[item] || 0) + 1

B freqCounter[item] += 1

C freqCounter[item] = 1

D freqCounter[item] = freqCounter[item] - 1

This safely initializes count to 0 if undefined, then adds 1.

What is the output frequency counter for array ['a', 'b', 'a']?

A {"b": 3}

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

C {"a": 3}

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

The letter 'a' appears twice, 'b' once.

Which problem can be solved efficiently using the Frequency Counter Pattern?

A Find the maximum element in an array

B Check if two strings are anagrams

C Sort an array

D Reverse a string

Anagrams have the same frequency of each character.

Explain how to use the Frequency Counter Pattern to check if two arrays have the same elements with the same frequency.

Think about counting each element's occurrences and then comparing.

Describe why using a hash map for frequency counting is more efficient than using nested loops.

Focus on how many times each element is processed.

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