Understanding the Frequency Counter Pattern in JavaScript

Introduction

Hey everyone! Today, I want to share a powerful problem-solving pattern called the Frequency Counter. It's a great way to compare data, like arrays and strings, by counting how often each value appears. Let's dive in!

Frequency Counter Problem Solving Pattern

The Frequency Counter pattern uses objects or sets to count the frequency of values. It is often used with arrays and strings. This pattern helps us store elements as keys in an object and their counts as values.

When to Use This Pattern?

Use this pattern to compare data, like checking if two strings are anagrams. It's great for problems where you need to compare different arrays or strings.

Why Use This Pattern?

Using Frequency Counters usually makes your code faster. Instead of using nested loops, which take O(N^2) time, you can reduce it to O(N) time. This pattern helps avoid nested loops and makes your algorithm more efficient.

Example Problem

Problem: Write a function called "same" that checks if every value in one array has its corresponding value squared in another array. The frequency of values must be the same (order doesn't matter).

Example

javascriptCopy
same([1, 2, 3], [4, 1, 9]); // true
same([1, 2, 3], [4, 1]); // false
same([1, 2, 1], [4, 4, 1]); // false (frequency must be the same)

Easier Solution with Nested Loops (O(N^2)):

javascriptCopy
const same = (arr1, arr2) => {
  if (arr1.length !== arr2.length) return false;

  for (let i = 0; i < arr1.length; i++) {
    const correctIndex = arr2.indexOf(arr1[i] ** 2);

    if (correctIndex === -1) return false;

    arr2.splice(correctIndex, 1);
  }

  return true;
};

Explanation:

1. Check if the arrays have different lengths.
2. Loop over the first array and find the index of the squared element in the second array.
3. If the element is not found, return false.
4. If found, remove that element from the second array.
5. If we loop through all elements without returning false, return true.

Refactored Solution with Frequency Counter (O(N)):

typescriptCopy
type frequencyObjT = {
  [key: string]: number;
};

const same = (arr1: number[], arr2: number[]): boolean => {
  if (arr1.length !== arr2.length) return false;

  const frequencyCounter1: frequencyObjT = {};
  const frequencyCounter2: frequencyObjT = {};

  for (let val of arr1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }

  for (let val of arr2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
  }

  for (let key in frequencyCounter1) {
    if (!frequencyCounter2[Number(key) ** 2]) return false;
    if (frequencyCounter1[key] !== frequencyCounter2[Number(key) ** 2])
      return false;
  }

  return true;
};

Explanation:

1. Create two frequency counters, one for each array.
2. Loop through each array and count the frequency of each value.
3. Check if each value in the first frequency counter has its squared value in the second frequency counter.
4. If all checks pass, return true. Otherwise, return false.

Summary

The Frequency Counter pattern is a great way to make your code more efficient by reducing time complexity from O(N^2) to O(N). It's especially useful for comparing arrays and strings. Give it a try in your next coding challenge!

Thank you for reading! I hope you found this article helpful!