Frequency Counter Solving Pattern

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.

Frequency Counter Pattern processes gif
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.

--

--

--

I am a junior web developer with strong passion for technologies and web development.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Ultimate Mac JavaScript & PHP development setup.

Connecting React to Express server

Open Sourcing Figment AR, a conference, and GLTF skeletal animation support!

Writing custom components in Compose — Part1 Multi Color Progress Bar

Firebase Multi-path Updates — Updating Denormalized Data in Multiple Locations

Quick Angular fix: the NgModule ‘AppModule’ needs to be compiled using the JIT compiler, but…

Tailwind CSS in HTML starter via NPM

Decisive React-ions to Volatile Scenarios

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jacopo Bacci

Jacopo Bacci

I am a junior web developer with strong passion for technologies and web development.

More from Medium

How to tackle Remote Pair Programming as a novice

Everyday Things: Binary Search Trees & the Recursive Search Algorithm

Sorting Techniques 1.0

Greedy Algorithm