Frequency Counter Algorithm Pattern(Go Example)
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.
- 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.
- Split both of the strings, so we can get an array of letters that composes the string.
- Initiate an empty map that we’ll use to store our characters in the first array.
- 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
- 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.
- 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!
