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.
Top comments (0)