Frequency Counter Algorithm Pattern

Frequency Counter Algorithm Pattern

by Kenny Porterfield | Sun, May 9 2021

Category: Data Structures & Algorithms

Patterns

When solving problems with code, there are some common and established patterns out there that exist that can help you get the job done. One such pattern that I'm going to write about today is called the frequency counter approach.

 

Frequency Counter

This pattern uses objects or sets to collect values and frequencies of values, and can help avoid the need for nested loops or O(N2) operations with arrays and/or strings.


Example Problem:
Write a function called same, which accepts 2 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.

 

Example Inputs/Ouputs

same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,1,4]) // false (must be same frequency)

 

Algorithm Walkthrough

First we will examine what we'll call a "naive" approach to solving this problem. It works, but it involves nested loops and the computer has to take many more steps to solve the problem than it has to, so it's an inefficient algorithm. Nested loops often results in O(N2) time complexity, which is what we see here. Any time we're looking at an O(N2) algorithm, it's worth exploring if there are any alternative options to make it more efficient.

 

"Naive" Algorithm - O(N2) time complexity with nested loops.

 

function same(arr1, arr2) {
    // If the lengths of the arrays aren't equal, the 
    // conditons can't be met so we return false
    if(arr1.length !== arr2.length) {
        return false;
    }
    // Loop over each index in the first array, checking 
    // to see what the index of its value squared is in the second array
    // If the squared value isn't present in the second array, 
    // indexOf will return -1, and we will return false
    for(let i = 0; i < arr1.length; i++) {
        let correctIndex = arr2.indexOf(arr1[i] ** 2);
        if(correctIndex === -1) {
            return false;
        }
        // If the squared value is in the second array, we will 
        // splice it out so that that same value can't be repeated
        // to ensure the frequency of values is the same
        arr2.splice(correctIndex,1);
    }
    // If we make it through the loop without returning false, 
    // then the conditions are met and we return true
    return true;
}

 

Let's take the frequency counter approach to solving this problem, and see how that improves upon the efficiency of the algorithm.

 

Frequency Counter Algorithm:

 

function sameRefactored(arr1, arr2) {
    if(arr1.length !== arr2.length) {
        return false;
    }
    // We use an object to count the frequency of 
    // individual values in the arrays
    let frequencyCounter1 = {};
    let frequencyCounter2 = {};
    // These for ... of loops count the frequency of 
    // individual values in the arrays
    for (let val of arr1) {
        // We check to see if our array value is a key in the object
        // If it is we add 1 to it, if it isn't we initialize it to 1
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
    }
    for (let val of arr2) {
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
    }
    // console.log our objects just to see them later on
    console.log(frequencyCounter1);
    console.log(frequencyCounter2);
    // For each key in the first object
    for(let key in frequencyCounter1) {
        // Is the key squared in the second object? If not, we return false
        if(!(key ** 2 in frequencyCounter2)) {
            return false;
        }
        // Do the values in the object correspond? 
        // This is how we check if the frequency is the same.
        // If not, return false
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
            return false;
        }
    }
    // If we never return false then our conditions are met, so return true
    return true;
}

 

With the frequency counter pattern, we use 2 objects to store the values in each array as the key, and the number of times those values occur. We are able to avoid nested loops by using 2 separate loops, which results in a time complexity of something like O(2N), which simplifies down to O(N), which is vastly better than O(N2) as the size of the data increases.

 

Here are another couple of examples of the frequency counter pattern at use in problems I solved on LeetCode recently.

 

Anagrams Algorithm

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

 

function validAnagram(str1, str2) {
    // If the lengths of the strings aren't the same, 
    // it won't be an anagram
    if(str1.length !== str2.length) {
        return false;
    }
    // We use an object to count the number of individual 
    // characters in the strings
    let characterCounter1 = {};
    let characterCounter2 = {};
    // Use for ... of loop on each string to count the 
    // number of each character in the string
    for (let char of str1) {
        characterCounter1[char] = (characterCounter1[char] || 0) + 1;
    }
    for (let char of str2) {
        characterCounter2[char] = (characterCounter2[char] || 0) + 1;
    }
    // console.log our objects just to see them later
    console.log(characterCounter1);
    console.log(characterCounter2);
    // For each key in the first object
    for(let key in characterCounter1) {
        // Does the key in the second object? If not, 
        // we return false
        if(!(key in characterCounter2)) {
            return false;
        }
        // Are the counts of each character the same 
        // in both objects?
        // If not, return false
        if(characterCounter2[key] !== characterCounter1[key]) {
            return false;
        }
    }
    // If it has met all of these conditions then we 
    // have an anagram, so return true
    return true;
}

 

Single Number In An Array

Given a non-empty array of integers, every element appears twice except one. Find that one.

 

function singleNumber(arr) {
    // If the length of the array is one, then we return the only value 
    // in the array
    if(arr.length === 1) return arr[0];
    // Initialize an object that we will use to count the number of
    // each value in the array
    let valueCounter = {};
    // For each value in the array, we check to see if exists as a key
    // If it does, we add 1 to it, if it doesn't we initialize it and set it to 1
    for (let val of arr) {
        valueCounter[val] = (valueCounter[val] || 0) + 1;
    }
    // For each key in the object, we check to see if the value equals 1
    // If it does, that's our single number, so we return that key
    for(let key in valueCounter) {
        if(valueCounter[key] === 1) {
            return key;
        }
    }
}

 

If any of this stuff didn't make sense, especially anything referring to Big O Notation (O(N), O(N2), etc.), go back and read my previous posts on Data Structures & Algorithms, especially Sorted Arrays, Binary Search, & Big O and Sorting Algorithms & Optimizing Optimistically. If you have those bases covered, I think everything here will make sense. If it still doesn't make sense or I got something wrong, let me know in the comments down below.

 

If you are interested in learning more, I'd encourage you to buy a copy of A Common-Sense Guide to Data Structures and Algorithms, by Jay Wengrow.



Check out other Data Structures & Algorithms blogs.

Comments

Login or create an account to leave a comment.

kenny_porterfield - May 10 2021

I solved another problem just this morning using the frequency counter approach. It looked like this: 


// CUBED SETS
/* Given an integer n, return true if n^3 and n have the same set of digits. */
// Example:
// sameDigits(1) // true
// sameDigits(10) // true
// sameDigits(251894) // true
// sameDigits(251895) // false

function sameDigits(num) {
    // Short circuit return true if the num is 1 or 0
    // so we don't have to go through the whole function
    if(num === 1 || num === 0) return true;
    
    // Find out what our input is cubed
    let numCubed = num * num * num;

    // Convert our numbers to strings so 
    // we can iterate through them with a for of loop
    num = num.toString();
    numCubed = numCubed.toString();

    // Declare variables for our objects that we'll use to store
    // the set of values
    let numCount = {};
    let numCubedCount = {};

    // Do a for of loop on our num and numCubed to create
    // a data structure that contains the set of values present 
    // in each
    for (let digit of num) {
        numCount[digit] = (numCount[digit] || 0) + 1;
    }
    for (let digit of numCubed) {
        numCubedCount[digit] = (numCubedCount[digit] || 0) + 1;
    }

    // Are the number of keys equal in each object?
    // If the result contains the same set of numbers
    // the # of keys should be equal
    // If they're not, one of the numbers contains a different
    // number than the other, so return false
    let numKeyCount = Object.keys(numCount).length;
    let numCubedKeyCount = Object.keys(numCubedCount).length;
    if(numKeyCount !== numCubedKeyCount) return false;

    // For each key in the first object
    for(let key in numCount) {
        // Does the key in the second object? If not, we return false
        if(!(key in numCubedCount)) {
            return false;
        }
    }

    // If we have the same # of keys and each key in the
    // first object has a corresponding key in the second
    // object, then they contain the same set of numbers
    // so we can return true
    return true;
}

Recent Blog Posts

Get in touch

Kenny Porterfield
kjport3@gmail.com
LinkedIn

Or, send me a message from here: