Frequency Counter Pattern Using Hash Map in DSA Typescript - 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.

How does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function frequencyCounter(arr: number[]): Record {
  const freqMap: Record = {};
  for (const num of arr) {
    freqMap[num] = (freqMap[num] || 0) + 1;
  }
  return freqMap;
}
    

This code counts how many times each number appears in the array and stores the counts in a hash map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element of the array once.
• How many times: Exactly once for each item in the array (n times).

How Execution Grows With Input

As the array gets bigger, the number of steps grows directly with the number of items.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows in a straight line with input size; doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to count frequencies grows directly with the number of items in the array.

Common Mistake

[X] Wrong: "Using a hash map makes counting frequencies take constant time no matter the array size."

[OK] Correct: While each insertion or update in the hash map is fast, you still have to look at every item in the array, so time grows with the array size.

Interview Connect

Counting frequencies efficiently is a common skill that shows you understand how to use hash maps to speed up problems that need counting or matching.

Self-Check

"What if the input array was already sorted? How would that change the time complexity of counting frequencies?"

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