### 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(N^{2}) 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(N^{2}) time complexity, which is what we see here. Any time we're looking at an O(N^{2}) algorithm, it's worth exploring if there are any alternative options to make it more efficient.

*"Naive" Algorithm* - O(N^{2}) 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(N^{2}) 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(N^{2}), 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.