# 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**

Write a function which accepts two arrays. The function should return true if every value in the array has it’s corresponding value squared in the second array. The frequency of values must be the same.

Outputs should look like: same([1,2,3], [4,1,9]) // true

same([1,2,3], [1,9]) // false

same([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 lengthif (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 stopif (correctIndex === -1) {

return false }// if the index does exist, clean the array (splice) until the array length is 0arr2.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:

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

bringing our **Big O **in this case to **n²**. 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 match

if (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 comparefor (let key in frequencyCounter1) {

// search for a squared key in second array for each key in array 1

if (!(key ** 2 in frequencyCounter2)) {

return false }// search for the values of the matching keys to make sure they are the same, if not stopif(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 trueelse {

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

Given two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

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 falseif (sameChar === -1) {

return false } }// all are matches, go ahead and return truereturn 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 **n²** 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 valueslet lookup = { };

// loop through one string and count the frequencies of each characterfor (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 keysfor (let i = 0; i < str2.length; i++) {

let letter = str2[ i ]// if there’s a key that doesn’t match, stop — return falseif ( ! (lookup[letter])) {

return false }

// if the key matches decrease its frequency value by 1else {

lookup[letter] = lookup[letter] — 1 } }// finish and return true when all frequency values decrease to 0return 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!*