DEV Community

Cover image for How to Compare Arrays in JavaScript Efficiently
Danny Adams
Danny Adams

Posted on

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.

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:

  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
}
Enter fullscreen mode Exit fullscreen mode

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,
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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!

Thanks for reading.

Have a great day!

Top comments (9)

Collapse
 
northerncaptain profile image
NorthernCaptain • Edited

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
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
doabledanny profile image
Danny Adams

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!

Collapse
 
costinmanda profile image
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.

Collapse
 
akhand3108 profile image
Akhand Patel

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

Collapse
 
costinmanda profile image
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?

Thread Thread
 
simonas88 profile image
simonas88

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

Thread Thread
 
costinmanda profile image
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.

Thread Thread
 
simonas88 profile image
simonas88

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.

Thread Thread
 
costinmanda profile image
Costin Manda

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.