# Frequency Counters — What are they and how they can help you solve algorithms with greater efficiency.

Frequency Counters — how they can help decrease time and space complexity in algorithms

In the middle of interviews and practicing never-ending algorithms, I’ve started to implement more than one solution to every problem. Mainly algorithms that require comparing two sets of arrays or objects to test similarities and differences.

Often, my direct solution involved nested loops to get to the answer. However, looking back at my solutions from a time and space complexity perspective (the Big O), these solutions were subpar. Yes, my solution outputs the correct result, but the larger the input the slower my algorithm becomes.

Let’s look at a couple of examples to test and see why using something other than nested loops can not only still derive the correct output, it takes exponentially faster time to compute.

# Algorithm 1

`Outputs should look like: same([1,2,3], [4,1,9]) // truesame([1,2,3], [1,9]) // falsesame([1,2,3], [4,4,1]) // false (must be same frequency)`

My initial ‘naive’ approach:

`function same(arr1, arr2) {// knockout future logic if the arrays do not have the same length  if (arr1.length !== arr2.length) {        return false }// loop through one arrayfor (let i = 0; i < arr1.length; i++) {// loop through second array using indexOf to see if index ** 2 existslet correctIndex = arr2.indexOf(arr[i] ** 2);//if the index doesn’t exist in the second array, return false and stop  if (correctIndex === -1) {       return false }// if the index does exist, clean the array (splice) until the array length is 0    arr2.splice(correctIndex, 1) {         return true } }`

This function will output true or false correctly depending on the input it is given. However, let’s get how many loops we are requiring to get to our final answer:

1. Loop through first array
2. 2. Nested loop through second array (indexOf is a nested loop)

bringing our Big O in this case to . Not so efficient in terms of time and space complexity.

Now, let’s look at the same problem but solve it with a different approach to avoid nested looping — with frequency counters:

`function same(arr1, arr2) {// like before, don’t continue further logic is array lengths do not matchif (arr1.length !== arr2.length) {     return false }// to count the frequency of each character in each array, declare two objects      let frequencyCounter1 = { };      let frequencyCounter2 = { };// loop through array1 and set key and values for each characterfor (let value of arr1) {frequencyCounter1[value] = (frequencyCounter1[value] || 0) + 1 }// loop through array1 and set key and values for each characterfor (let value of arr2) {frequencyCounter2[value] = (frequencyCounter2[value] || 0) + 1 }//sets the counts into two objects, now compare// search for a squared key in second array for each key in array 1   for (let key in frequencyCounter1) {       if (!(key ** 2 in frequencyCounter2)) {            return false }// search for the values of the matching keys to make sure they are the same, if not stop       if(frequencyCounter2[key**2] !== frequencyCounter1[key]) {             return false } // if all goes through, the keys on the second array and squared values of the first array and the values are the same, go ahead and return true            else {              return true } }`

At first, this solution looks much longer and if you’re looking at it for the first time it may even take a bit of time to correctly understand what’s going on. However, putting the logic to the side and actually counting the loops in this solution to achieve a big idea picture of time/space complexity you’ll see that there are only 2 loops. It doesn’t matter how long the arrays are; each array will only be looped through once. Then there is a search method within an object, which takes very little time (one of the quickest processes to receive information from objects). This concludes the solution to have a Big O of (2n) which we can round to just (n).

As you can see a little more clearly now (hopefully!) that our second approach is significantly faster than our initial approach. Let’s take a look at another example to further clarify this conclusion.

# Algorithm 2

Initial approach:

`function isValidAnagram(str1, str2){// knockout further logic if strings do not match in lengthif(str1.length !== str2.length) {       return false }// loop through one arrayfor (let i = 0; i < str1.length; i++) {//check if each instance of i matches an index of second stringlet sameChar = str2.indexOf(str1[i])//if there is no match, stop — return false   if (sameChar === -1) {        return false }  }// all are matches, go ahead and return true       return true } }`

‘Short and Sweet?’ Is something I hope you’re not thinking if you’ve read this far. Although this will output true if both strings consist of the same character frequencies and false if not; the big O of this solution is due to the nested looping over the second string using the built-in method indexOf.

Let’s look at an approach to this problem with a frequency counter:

`function isValidAnagram(str1, str2) {// do not go further if the lengths of both strings are not equalif(str1.length !== str2.length) {       return false }// declare an object that will set up the characters as keys and its frequencies as values let lookup = { };// loop through one string and count the frequencies of each character      for (let i = 0; i < str1.length; i++) {          let letter = str1[ i ]// add these values to the ‘lookup’ objectlookup[ letter ] ? lookup[letter] + 1 : lookup[letter] = 1 }// now loop through second string and check to see if the ‘lookup’ object consists of the same keys      for (let i = 0; i < str2.length; i++) {           let letter = str2[ i ]// if there’s a key that doesn’t match, stop — return false   if ( ! (lookup[letter])) {              return false }        // if the key matches decrease its frequency value by 1             else {       lookup[letter] = lookup[letter] — 1 } }// finish and return true when all frequency values decrease to 0   return true } }`

This solution loops through both strings once depending on how big the string length (n) is. It notes all its findings in an object, to search through later — this as we stated previously, doesn’t take much time bringing the Big O of this solution to (n).

I hope that taking a closer look at both of these algorithm solutions justify that using something like a frequency counter to note similarities or differences between two data structures takes up much less time and space (when speaking of big O) and thus much more efficient.

Good luck to all those practicing algorithms and hope that this is of benefit!

Recent software engineering graduate who enjoys exploring the intersection between business and code.

## More from Saman Batool

Recent software engineering graduate who enjoys exploring the intersection between business and code.