Frequency Counter Pattern Using Hash Map in DSA Typescript - Execution Trace

Concept Flow - Frequency Counter Pattern Using Hash Map

Start with empty hash map

↓

Read next element from input array

↓

Check if element in hash map?

No→Add element with count 1

↓

Increment count

↓

Repeat for all elements

↓

Hash map now holds frequency counts

↓

Use frequency counts as needed

↓

End

We read each element, check if it exists in the hash map, add or increment its count, and repeat until all elements are processed.

Execution Sample

DSA Typescript

const arr = ['a', 'b', 'a', 'c', 'b', 'a'];
const freqMap = new Map<string, number>();
for (const char of arr) {
  freqMap.set(char, (freqMap.get(char) ?? 0) + 1);
}
console.log(freqMap);

Counts how many times each character appears in the array using a hash map.

Execution Table

Step	Operation	Element Processed	Hash Map State	Visual State
1	Start	-	{}	{}
2	Process element	'a'	{ 'a': 1 }	{ 'a': 1 }
3	Process element	'b'	{ 'a': 1, 'b': 1 }	{ 'a': 1, 'b': 1 }
4	Process element	'a'	{ 'a': 2, 'b': 1 }	{ 'a': 2, 'b': 1 }
5	Process element	'c'	{ 'a': 2, 'b': 1, 'c': 1 }	{ 'a': 2, 'b': 1, 'c': 1 }
6	Process element	'b'	{ 'a': 2, 'b': 2, 'c': 1 }	{ 'a': 2, 'b': 2, 'c': 1 }
7	Process element	'a'	{ 'a': 3, 'b': 2, 'c': 1 }	{ 'a': 3, 'b': 2, 'c': 1 }
8	End	-	{ 'a': 3, 'b': 2, 'c': 1 }	{ 'a': 3, 'b': 2, 'c': 1 }

💡 All elements processed, frequency counts complete.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
freqMap	{}	{ 'a': 1 }	{ 'a': 1, 'b': 1 }	{ 'a': 2, 'b': 1 }	{ 'a': 2, 'b': 1, 'c': 1 }	{ 'a': 2, 'b': 2, 'c': 1 }	{ 'a': 3, 'b': 2, 'c': 1 }	{ 'a': 3, 'b': 2, 'c': 1 }
char	-	'a'	'b'	'a'	'c'	'b'	'a'	-

Key Moments - 3 Insights

Why do we check if the element exists in the hash map before adding or incrementing?

Because if the element is not yet in the map, we need to add it with count 1. If it exists, we increase its count. This is shown in execution_table rows 2 and 4 where 'a' is added first, then incremented.

What happens if the input array is empty?

The hash map remains empty as no elements are processed. This is like step 1 and 8 in the execution_table where no changes occur.

Why do we use (freqMap.get(char) ?? 0) + 1 instead of just freqMap.get(char) + 1?

Because freqMap.get(char) returns undefined if the element is not present, and adding 1 to undefined causes errors. Using ?? 0 ensures we start counting from zero. This is critical in step 2 when 'a' is first added.

Visual Quiz - 3 Questions

Look at the execution_table, what is the frequency count of 'b' after step 5?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Hash Map State' column at step 5 in the execution_table.

At which step does the frequency count of 'a' become 3?

A Step 6

B Step 7

C Step 4

D Step 5

💡 Hint

Look at the 'Hash Map State' column for 'a' in the execution_table rows.

If the input array had no 'c', how would the final hash map state change?

A { 'a': 3, 'b': 2, 'c': 1 }

B { 'a': 3, 'b': 2, 'c': 0 }

C { 'a': 3, 'b': 2 }

D {}

💡 Hint

Refer to the final 'Hash Map State' in execution_table and consider absence of 'c'.

Concept Snapshot

Frequency Counter Pattern Using Hash Map:
- Initialize empty hash map
- For each element in input:
  - If element not in map, add with count 1
  - Else increment existing count
- Result: map holds frequency of each element
- Useful for counting, comparisons, and validations

Full Transcript

The Frequency Counter Pattern uses a hash map to count how many times each element appears in a list. We start with an empty map. For each element, we check if it is already in the map. If not, we add it with count one. If yes, we increase its count by one. This continues until all elements are processed. The final map shows the frequency of each element. This pattern helps solve problems involving counting or comparing elements efficiently.

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