Problem Solving Patterns: Frequency Counter

This article is a continuation of the problem solving patterns series. In the previous articles in this series, I explained my preferred approach to solving problems and introduced a common pattern: the multiple pointers pattern. Today we’re going to touch on the frequency counter pattern.

The Frequency counter pattern is used to collect values and the frequency the values appear in a data structure usually in javascript we use objects. This technique can often avoid the need for nested loops with strings and arrays. Nested loops should be avoided when necessary because they increase the time complexity of a function. Okay, let us take a look at an example.

For this example we’re going to create a function that accepts two arrays and should return true or false depending if every value in the second array is the same as the first array but squared. It shouldn’t matter how the arrays are sorted as long as they have the same frequency of appearance. The objects should store each element in the array as keys and the frequency they appear as the values. In the function we need to compare each key and value in both the objects. Let’s begin!

function same(arr1, arr2){
//First lets check if the arrays are the same length and if their not return false
    if(arr1.length !== arr2.length){
        return false;
    }
// next we declare the two objects that will store our info.
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}
// Now, loop through each array and push each element in the array to the empty object. 
  for(let val of arr1){
//This little beauty here adds the value in the object and if it already exists it adds one to the value in the key/value pair. 
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }
    for(let val of arr2){
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1        
    }
//Up until this point, the frequency counter pattern is everything before and after this is the logic to complete the function. 
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}
same([1,2,3], [4,1,9]) // returns true 
same([1,2,3,2,5], [9,1,4,4,11]) // returns true
 

This is one of the most useful patterns in my opinion, technical interviewers love to ask interviewees to write anagram functions that returns true or false. If the first string is an anagram of the second string return true. You can see this pattern solves this function very easily. You’re welcome. Thanks for reading!