Frequency Counter Algorithm Pattern(Go Example)

Image from Shutterstock

Why should we use it?

There are many different ways to approach solving problems. However usually, the most obvious ones aren’t the optimal solution. An example would be using nested loops. We call this the brute force method or the naive approach, and the reason these aren’t optimal solutions is that they are very slow. These solutions run at quadratic time(O(n²) Time complexity). The frequency counter pattern looks to give us a solution that is usually a lot faster(Typically at Linear Time; O(n) Time Complexity).

How does it work?

How the frequency pattern works is you would get a collection of data and store them within objects or maps with the key being the element we’re keeping track of and the value being the number of occurrences we run into that element. With this data, we can do things like comparing two arrays or finding the first duplicate, and many other common problems you may run into.

Example

Here is an example question where using the frequency counter pattern might be a good approach!

Given two strings, write a function to determine if the second string is an anagram of the first. If it is an anagram return true, if not return false.ex: 
validAnagram(“helloworld”, “oowldlrhle”) //true
validAnagram(“racecar”, “racekar”) //false

Before we write out any code, let's plan out the steps we should take to come to a viable solution.

  1. Create a check to see if the strings are of the same length, if they are not we know it’s not an anagram and we should return false.
  2. Split both of the strings, so we can get an array of letters that composes the string.
  3. Initiate an empty map that we’ll use to store our characters in the first array.
  4. Iterate through each letter of the first string and place them in the map with the key being the character and value being the number of occurrences
  5. Iterate through the second string and lookup to see if the map contains all the letters within the second string, If there are any that do not exist within the map, return false.
  6. Otherwise, return true because the number of occurrences for each letter within the second string matches up with the ones in the first string.

Now that we have a solid plan, now let’s write out some code!

Hope this helped in understanding use cases for this pattern and why would want to take this approach to solve algorithms. As always Happy Coding!

--

--

--

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

Recommended from Medium

SSO (aka S.S.Octopus) is one year old!

SSO (S.S. Octopus) logo with a birthday cake, confetti in the background

Getting started with conventions in Python

This Is Us

🧟 AutoShark welcomes RugZombie to the Ocean Ecosystem!

npx: npm package runner

No, you don’t need a screen to learn to code. Robot Turtles is how.

Meet a Booleaner — Geeta

Look ma, no Servers!

Some notepads kept over a round table at the Geek Night event

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
Sean Dever

Sean Dever

More from Medium

How to Check nil Interface in Golang?

Pointer assignment is not atomic in Go

Getting started with GO Programming Language — Part Two

【Go】Implement SHA256, encryption and hashing in Go