In this article, I’m going to show you two ways of solving a typical interview-style question. The first solution is more obvious and less efficient. The second solution introduces a great problem-solving tool: frequency counter objects, which greatly improves the efficiency.

Here’s what you’ll gain from reading this article:

- A framework for approaching problems
- A very useful, highly performant problem solving technique
- An improved ability to analyse functions and improve performance

I also made a YouTube video for those that like video. If you enjoy the video, consider subscribing to my channel.

## The problem

“Write a function called “squared” which takes two arrays. The function should return true if every value in the array has its value squared in the second array. The frequency of values must be the same.”

-- Your interviewer

At first, I will show you the “Naïve” way of solving the problem – the more obvious way that isn’t efficient.

I’ll then show you an efficient way to solve the problem using “frequency counter objects”. This is a very handy technique to have in your problem-solving toolbox (your brain).

## Understanding the problem

**Problem solving 101:** Before we attempt to write a solution, it’s very important to understand the problem - to give some examples and the results we expect. We can then use these examples as tests to ensure our solution is working correctly.

**Examples:**

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

**Example 1 is true because:**

- 1
^{2}= 1 (yep, that’s in array 2) - 2
^{2}= 4 (yep, that’s in array 2) - 3
^{2}= 9 (yep, that’s in array 2)

**Example 2 is false because:**

- 1
^{2}= 1 (yep, that’s in array 2) - 2
^{2}= 4 (yep, that’s in array 2) - 3
^{2}= 9 (nope, that's not in array 2)

**Example 3 is false because:**

- 2
^{2}= 4 (yep that’s in array 2) - 2
^{2}= 4 (nope, there is only one 4 in array 2) - 3
^{2}= 9 (yep, but we won’t even get to this check because the function returned false beforehand)

## The “naïve” way

First, we check if the arrays are not equal length. If not, we return false and get out of the function early because the frequency of values can’t possibly be the same.

Next, we loop over each number (num) in arr1. Inside the loop, we use `indexOf()`

to look for the position of `num2`

in arr2. The value is assigned to the variable `foundIndex`

.

If the value was not found, indexOf returns -1. So, we can check if foundIndex = -1, and return false if so.

If all is good, we move on and remove this value from arr2 using the `splice()`

method. This ensures the frequency of values in both arrays are the same.

After looping over each number, and all the checks pass, we can return true.

```
function squared(arr1, arr2) {
if (arr1.length !== arr2.length) return false
for (let num of arr1) {
let foundIndex = arr2.indexOf(num ** 2)
if (foundIndex === -1) return false
arr2.splice(foundIndex, 1)
}
return true
}
```

## Performance

This algorithm has a Big O(n^{2}) because we loop over every single item in the first array, then inside this loop, we are looping over every single item in the second array (with `indexOf()`

) at worst-case.

If you don’t know (or have forgotten) what Big O is, check out this video: Big O Notation in JavaScript. It’s an important topic!

If the arrays are of length n, then the number of operations will be n * n = n^{2}. Hence Big O(n^{2}).

Now, this is not quite true because the second array becomes shorter on each loop, so on average we will only loop over half the second array (0.5n). The Big O will be of n * 0.5n = 0.5n^{2}. But Big O looks at big picture stuff, and as the input approaches infinity, the 0.5 will be insignificant and so we simplify to Big O(n^{2}).

## A smarter way – Frequency Counter Objects – Big O(n)

### What are Frequency Counter Objects?

Frequency counters are objects that tally things up. Here’s two examples of where they would be useful:

- The number of times a character appears in a string
- The number of times a number appears in an array

Using frequency counters can also significantly improve the performance of an algorithm, as it can often remove the need to use nested for-loops.

Here’s what the frequency counter object for [1, 2, 3, 4, 3] would look like:

```
let frequencyCounter = {
1: 1,
2: 1,
3: 2,
4: 1,
}
```

All the numbers appear once, apart from 3, which appears twice.

### The solution

To create a frequency counter object, we loop over the array in question. We then create a key and give it a value of the current value + 1, or if it’s the first time we’ve encountered this number, `frequencyCounter[num]`

will be undefined and so we initialise the value to 1.

I used two for…of loops as I felt it was easier to read, but it could also be done with just one for-loop.

The frequency counter objects can then be compared. We first check if each key squared from frequency counter 1 is a key in frequency counter 2. If not, return false.

Next, we check if the frequencies (values) are equal. If not, return false.

And if we get through all this unscathed, we get to the bottom and return true.

```
function squared(arr1, arr2) {
if (arr1.length !== arr2.length) return false
let frequencyCounter1 = {}
let frequencyCounter2 = {}
// Create frequencyCounter1
for (let num of arr1) {
frequencyCounter1[num] = frequencyCounter1[num] + 1 || 1
}
// Create frequencyCounter2
for (let num of arr2) {
frequencyCounter2[num] = frequencyCounter2[num] + 1 || 1
}
// Compare frequency counters
for (let key in frequencyCounter1) {
if (!(key ** 2 in frequencyCounter2)) return false
if (frequencyCounter1[key] !== frequencyCounter2[key ** 2]) return false
}
return true
}
```

## Performance

- To create frequencyCounter1, we loop over all the numbers in arr1 => n loops
- Same for frequencyCounter2 => n loops
- To compare the frequency counters, we loop over all the keys in frequencyCounter1 => at worst case, n loops

Total = n + n + n = 3n

Resulting in a Big O(n) – linear time complexity.

Much better than our first effort of with Big O(n^{2}) – quadratic time complexity.

## Awesome references

- I can attribute almost all of my knowledge of algorithms and data structures to one outstanding course: JavaScript Algorithms and Data Structures Masterclass by Colt Steele.
- If you prefer books: JavaScript Data Structures and Algorithms: An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals by Sammie Bae

If you enjoyed this post, consider subscribing to my YouTube channel - it would be much appreciated!

Thanks for reading.

Have a great day!

## Discussion (9)

Great article but I'm wondering why 3*n complexity is the best?

Why do you use 3 loops to get the results? It seems we can do this with two loops and 2*n complexity:

Yeah, your solution looks good, best case complexity is 2n.

I could've used one loop to create both frequency counter objects to reduce it down to 2n, but used two loops as I felt it was easier to see what was going on for readers. In hindsight, perhaps I should've just used the one.

Thanks for reading!

You calculate the complexity of code ignoring the code that gets/sets a value in an object. Also you ignore the memory complexity.

JS objects are like hashmaps, so insertion is O(1).

And reading from them, so you can increment them? Wouldn't a sorting in place of both arrays and then one iteration on both yield the same result faster and without extra memory?

No extra memory implies that the argument variable is mutated in sorting step. I wonder if that is okay.

Sure. Depends on the requirements. You could add 2n for copying the arrays, I suppose. I am not even saying that's it's the best way, but I think it's better than the one in the post.

Nevermind the intricacies of memory complexity, I think the point of the post was to demonstrate the technique of frequency counting which might be the way to go in some similar problem.

The post is called "How to Compare Arrays in JavaScript Efficiently". And I agree that count sort is a particular algorithm that might be useful in this case, but not frequency counting, which is just needlessly counting duplicates when that was not the requirement of the task.

I also think in any content that claims "A smarter way" one should consider all concerns, including memory consumption.