Have you ever solved algorithm problems, and while looking at the code you noticed some similarities in the algorithm of the particular problem, with an algorithm problem you solved some time ago, yea right, those similarities you noticed are called patterns. Logically they are a lot of patterns out in the world just to name a few.

• Divide and conquer.

• Greedy algorithm.

• Window sliding.

• Backtracking.

• Multiple pointers.

• Frequency counter.

The benefit of patterns in programming

Patterns in programming have come to stay because it offers a lot of benefits such as:

• Making it easier to solve new challenges

• Makes it Easy to make better coding decisions.

• Reducing the tendency of reinventing the wheel

• Writing efficient code

Use case of the frequency pattern

I called this pattern, frequency counter because its implementation has to do with counting the number of occurrences in an array or a given input. It is used when you are comparing two sets of values and checking the occurrence of certain elements in the sets of values given, for instance comparing if two arrays are similar, checking if two strings are anagrams etc.

One thing that distinguishes the frequency counter pattern from another method used in solving the above use case, is that the frequency pattern gives a time efficiency of O(n) (linear), compared to other methods that might give efficiency of O(N2) or O(nlogn). The frequency counter store the occurrence/frequency of elements in an object so as to easily compare them with other stored occurrence/frequency as an object.

The algorithm behind frequency counter pattern

We will be using a problem case, implementing the solution using a naive approach, and then using the frequency pattern.

Problem: Write a function called same, which accepts two arrays. The function should return true if every value in the array has its corresponding value squared in the second array. The frequency of values must be the same.

example: input and expected output
same([2, 5, 1, 3], [25, 4, 9, 2])  // return true
same([6,1,6], [36, 1]) // return false
same([1, 4, 6], [16, 1, 36]) //return true

// naive solution

function same(arr1, arr2){
    if (arr1.length !== arr2.length) return false
    arr1 = arr1.sort((a,b) => b - a);
    arr2 = arr2.sort((a,b) => b - a);

    let length = arr1.length - 1
    for(let i=0; i <= length; i++){
        let arrSquare = arr1[i] * arr1[i];
        if (arrSquare !== arr2[i]) return false
    }
    return true
}

same([1, 2, 3, 2], [4, 1, 4, 9])

from the solution above, you can see it solves the problem at hand but looking closely in terms of code efficiency it has an O(nlogn) time complexity, which is not really a bad start but they are ways to improve, lets take a look at the frequency counter pattern below.

// Frequency counter pattern solution

function same(arr1, arr2){
    if (arr1.length != arr2.length) return false

    let frequency_counter1 = {}
    let frequency_counter2 = {}

    for(let key of arr1){
        frequency_counter1[key] = ++frequency_counter1[key] || 1
    }

    for(let key of arr2){
        frequency_counter2[key] = ++frequency_counter2[key] || 1
    }

    console.log(frequency_counter2)
    for(let key in frequency_counter1){
        if(!(key**2 in frequency_counter2)) return false
        if (frequency_counter1[key] !== frequency_counter2[key**2]) return false
    }

    return true
}

same([1, 2, 3, 2], [4, 1, 4, 9])

The frequency counter pattern solution solves the problem with O(n) which is faster than that of O(n log n).

Let's apply some dry (Don't Repeat Yourself) code to the frequency counter code. so we would not be repeating the counter loop for both frequency_counter1 and frequency_counter2

function createFrequencyCounter(arr){
    frequency_counter = {}
     for(let key of arr){
        frequency_counter[key] = ++frequency_counter[key] || 1
    }
    return frequency_counter
}

function same(arr1, arr2){
    if (arr1.length != arr2.length) return false

    let frequency_counter1 = createFrequencyCounter(arr1)
    let frequency_counter2 = createFrequencyCounter(arr2)
    console.log(frequency_counter2)
    for(let key in frequency_counter1){
        if(!(key**2 in frequency_counter2)) return false
        if (frequency_counter1[key] !== frequency_counter2[key**2]) return false
    }

    return true
}

same([1, 2, 3, 2], [4, 1, 4, 9])

There you have it, The new power you just got, use it for good 😀.

Learn 4 steps in solving any algorithm challenge