Frequency Counter Pattern

What is the Frequency Counter Pattern?

It's a pattern that uses Objects, sets to inspect the frequencies of values.

You want to use this pattern when comparing inputs to multiple data, like [anagrams](https://en.wikipedia.org/wiki/Anagram.

It's also useful to avoid quadratic time complexity O(n²) since the Frequency Counter Pattern has a complexity of O(n).

Example with squared numbers

One of the easiest examples used to explain the Frequency Counter pattern is creating a function that takes 2 array and compare the values of the arrays. It should return true if the corresponding value squared in the other array. It will return false if the frequency of the values is not the same.

isSquaredFrequency([1,2,3], [9,1,4]) // True

Even not in the order each value has its corresponding squared value in the second array.

isSquaredFrequency([1,3,4], [1,16]) // False

The value of 3 squared is not in the second array.

isSquaredFrequency([3,3,2,1], [9,4,4,1]) // False

The frequency doesn't match since the number 2 is included in the first array, but 2 squared (4) is present twice in the second array. It doesn't match the frequency.

Making the isSquaredFrequency Function

isSquaredFrequency() should compare both array length and compare each index.

To do that we could use a solution with nested loops.

Therefore nested loop has a quadratic time complexity, so let's use the frequency counter pattern to create our function.

It's often better to have multiple for loop instead of nested loops.

If n is equal to 100 then you loop through n 100 times for each (for loop).

If n is equal to 100 then you loop through with a nested loop. You will loop n * n times so 100 * 100 = 10,000.

function  isSquareFrequency(arr1,arr2) {
    // compare arrays length
    if(arr1.length !== arr2.length) return false;
    // create 2 counter
    let counter1 = {}
    let counter2 = {}

    // looping through each array x on x times
    // and store the number of time each value appears in the 
    // array
    for (let val of arr1) {
      counter1[val] = (counter1[val] || 0) + 1
    }
    for (let val of arr2) {
      counter2[val] = (counter2[val] || 0) + 1
    }


    // check is there is the value counter1 key squared in the 
    // counter 2, then check if the number of values correspond
    // in the counter1

    for (let key in counter1) {
      if(!(key ** 2 in counter2)) return false;
      if (counter2[key ** 2] !== counter1[key]) return false;
    }
    return true;
  }

let array1 = [1,1,3,3,3] 
let array2 = [1,2,9,9,9]
let array3 = [1,1,9,9,9]

console.log(isSquareFrequency(array1,array2)) // return false
console.log(isSquareFrequency(array1,array3)) // return true

Using an object instead of an array we can deconstruct an array, so we can compare other values more easily.

Anagram

Anagrams are one of the most asked questions during interviews, as you can see here: https://stackoverflow.com/questions/909449/anagrams-finder-in-javascript

The frequency counter pattern can help us to solve this problem in a very elegant way and with O(n) time complexity.

Example.

function isAnagram(firstString,secondString) {
 // check if both strongs have same length 
  if (firstString.length !== secondString.length) return false; 

  // create object to store the key value of each letter to 
     decompose the string
  let anagram = {}; 

  // loop through the first string and decompose the string into an object
  for (let i = 0; i < firstString.length; i++ ) {
    let char = firstString[i];
    // check if the letter exist and if more than 1 increment the 
    // key/value, if character in anagram is true, add 1, if false 
    // then only 1 character so char = 1 
    anagram[char] ? anagram[char] +1 : anagram[char] = 1; 
  }

  // second loop to go through the second string 
  for (let i = 0; i < secondString.length; i++) {
    let char = secondString[i];
    // check for the letter. if none then false, otherwise 
   // continue looping, 
    if (!anagram[char]) {
      return false;
    } else {
      anagram[char] -= 1;
    }
  }
  return true;
}

console.log(isAnagram('dog','gd')); // false
console.log(isAnagram('cat','tac')); // true

We can decompose the object anagram to see how it looks like.
{d: 1, o: 1, g: 1}
Each time we loop if the character is present, then we subtract the char that match.

First loop: {d: 0, o: 1, g: 1}
Second loop: {d: 0, o: 0, g: 1}
Third loop: {d: 0, o: 0, g: 0}

Then will return true.

Conclusion

There are not many resources available about the Frequency Counter Pattern. I invite you to check more about!

Feel free to @ me on Twitter with your opinion & feedback about my article; Constructive feedback is always welcome.