Frequency Counter Solving Pattern

A different approach to compare multiple inputs' algorithms

Sometimes common patterns’ algorithm can come in handy, and they can be applied to multiple problems, they can be seen as common approaches to write code, like a sort of archetypes of problems or programming mechanisms everyone can use.

Knowing some of them, it might help you to solve more easily some challenges you have to face and to be ready for possible interviews.

Some of these patterns have ‘official names’ recognized by the community, while others don’t have necessarily renowned names, but the concepts might be well-known.

In this article we are exploring a pattern which is slightly more hidden than the others, in terms of fame, but that presents some advantages when you have to compare two inputs in your algorithm challenges.

The Frequency Counter pattern often avoids the need for nested loops when you deal with arrays or strings inputs comparisons. In fact, the resulting time complexity is usually O(n), instead of the easier solution which is going to give us O(n²) quadratic time, according to Big O notation.

Big O speaks about how much more “work” will an algorithm have to perform as its input size gets larger.

The core of the frequency counter pattern is to use objects or sets to collect a bunch of values and their frequencies and use them to compare the inputs.

Below are some examples using JavaScript, but the algorithm can obviously be implemented in any language.

To explain the concept of this pattern, I will take as example an algorithm that asks to find if an anagram is true or not, given two strings as inputs.

Here is the naive solution using nested loops.

In this example the nested loop is given by the indexOf method which is itself looping over the array to find the indexes, so the result is O(n²) time complexity.

Here instead the solution using frequency counter pattern.

As you can see, the time complexity here is O(2n) which resolves in O(n) because the two loops are processing in parallel, instead of inside one another.

Here’s a recap:

1. check if the length is the same
2. define empty object
3. loop over first input and increment the value if it exists or set it to one if it doesn’t
4. compare the characters of the second string to the object values, and subtract 1 if we found the same character
5. if a character is not present in the object, return false directly
6. also, if a character is already at 0, (e.g. when you have a double character) return false, as !0 is truthy
7. return true at the end

To understand better all the passages, I ran the function using Node.js debugger from VS Code. As you can see, the compiling of the object goes up and down, starting from adding and finishing by subtracting characters, until each value is 0 and the function returns true.

isAnagram function debugged in VS Code

For this article, I took inspiration from the online course JavaScript Algorithms and Data Structures Masterclass by Colt Steele, which I highly recommend.