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]) // 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 length
if (arr1.length !== arr2.length) {
return false }
// loop through one array
for (let i = 0; i < arr1.length; i++) {
// loop through second array using indexOf to see if index ** 2 exists
let 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 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 character
for (let value of arr1) {
frequencyCounter1[value] = (frequencyCounter1[value] || 0) + 1 }
// loop through array1 and set key and values for each character
for (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 length
if(str1.length !== str2.length) {
return false }
// loop through one array
for (let i = 0; i < str1.length; i++) {
//check if each instance of i matches an index of second string
let 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 equal
if(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’ object
lookup[ 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.

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