Coding Pattern - Frequency counter

March 29, 2023

This pattern uses objcts or sets to collect values and how much is repeated within certain structure.

This can often avoid having algorithms with complexities O(n) that required nested loops

Example Write a function which returns true if every value in the array has a corresponding value squared in a second array. The frequency of values must be the same.

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

// naive implementation
// We can start by using nested loops
function squared(arr1, arr1) {
	if(arr1.length !== arr2.length) {
		return false
	}
	for(let i = 0; i < arr1.length; i++) {
		let correctIndex = arr2.indexOf(arr1 ** 2)
		if(correctIndex === -1) {
			return false;
		}
		arr2.splice(correctIndex, 1);
	}
	return true;
}

What is the complexity of the example above?

O(n) for the first for loop
O(n) for the nested splice, this will reindex the array every time

Which means we have a O(n^2)

Refactored with the frequency counter pattern

// We will be implementing O(n) solution
function squared(arr1, arr2){
    if(arr1.length !== arr2.length)
        return false;
    }

    let frequencyCounter1 = {}
    let frequencyCounter2 = {}

    for(let val of arr1){
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }

    for(let val of arr2){
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1        
    }

    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }

        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}