## DEV Community is a community of 888,741 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # How to Compare Arrays in JavaScript Efficiently

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.

• 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.”

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:

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

Example 1 is true because:

• 12 = 1 (yep, that’s in array 2)
• 22 = 4 (yep, that’s in array 2)
• 32 = 9 (yep, that’s in array 2)

Example 2 is false because:

• 12 = 1 (yep, that’s in array 2)
• 22 = 4 (yep, that’s in array 2)
• 32 = 9 (nope, that's not in array 2)

Example 3 is false because:

• 22 = 4 (yep that’s in array 2)
• 22 = 4 (nope, there is only one 4 in array 2)
• 32 = 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(n2) 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 = n2. Hence Big O(n2).

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.5n2. 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(n2).

## 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:

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

1. To create frequencyCounter1, we loop over all the numbers in arr1 => n loops
2. Same for frequencyCounter2 => n loops
3. 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(n2) – quadratic time complexity.

## Awesome references

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

Have a great day!

## Discussion (9) NorthernCaptain • Edited on

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:

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

let frequencyCounter2 = {}

// Create frequencyCounter2
for (let num of arr2) {
frequencyCounter2[num] = frequencyCounter2[num] + 1 || 1
}

// Count values from arr1 against frequency counter of arr2
for (let val of arr1) {
let square = val ** 2
if (!(square in frequencyCounter2)) return false

// Decrease frequency counter for our value
let counter = frequencyCounter2[square] - 1
if (counter < 0) return false
frequencyCounter2[square] = counter
}

return true
}
`````` 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. Costin Manda

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

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? Costin Manda

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.  