Algorithm practice: Find common elements in two arrays

23 Sep 2019 - John

Continuing the algorithm practice saga, I bumped into an exercise that illustrates the "brute force/ideal/best" scenarios when solving algorithm exercises. As we know, there are not only multiple ways to reach an answer, but just because our answers work it doesn’t mean they’re optimal.

The problem

Given two arrays, create a function that lets a user know (true/false) whether two arrays contain any common items.
So for example, if we’re given two arrays: ['a', 'b', 'c', 'x'] and ['w', 'x', 'y', 'z'], our function should return true because both arrays contain the string 'x'.

Step 0: Divide and conquer

Before we even begin to think in code, we must understand the problem and be able to walk through it in plain English:

• We need to grab every element of the first array
• Then we need to compare each element we grab against every element of the second array.
• If we find a match, return true.
• If we find no matches, return false.

Step 1: the brute force approach

const array1 = ['a', 'b', 'c', 'z'];
const array2 = ['w', 'x', 'y', 'z'];
areTheyRelated = (arr1, arr2) => {
  for(element1 of arr1){
    for(element2 of arr2) {
      if(element1 === element2){
        return true;
      } else {
        continue;
      }
    }
  }
console.log('No match found.');
}

Can’t get any simpler. We’re looping over the first array and then we’re comparing its elements over every element of the other array. This solution works, but it is completely unacceptable due to the fact that we’re having a for loop, which is O(n), inside another for loop that is also O(n), thus rendering our function performance to O(n²).

Step 2: A somewhat more refined approach

For this approach, we disassemble our first array and put its contents inside an object as boolean values declared as true. Then we compare each element of the second array. If any value turns out to be truthy, we have a match:

const array1 = ['a', 'b', 'c', 'z'];
const array2 = ['w', 'x', 'y', 'z'];
areTheyRelated2 = (arr1, arr2) => {
  let obj = {};
for(element of arr1){
  if(!obj[element]){
    obj[element] = true;
  }
}
for(element of arr2){
  if(obj[element]){
    return true
  }
}
console.log('No match found.');
}

Step 3: The holy grail

While this is not always going to be the case, we should always strive to look for room for improvement. Our second approach has an acceptable performance of O(n), but is there a way to make it even more efficient? Let’s find out. We can just iterate over the first array using some() and then checking for a match using includes():

const array1 = ['a', 'b', 'c', 'z'];
const array2 = ['w', 'x', 'y', 'z'];
areTheyRelated3 = (arr1, arr2) => {
  console.log(arr1.some(item => arr2.includes(item)));
}

By taking this route we apparently improved our time complexity from an acceptable O(n) to an ideal O(1). However, think about what’s going on. We’re still iterating over the first loop by using some() and then we’re going through every element of the second array, effectively taking our already acceptable O(n) to O(n²).It is important to note that to arrive to this kind of solution takes practice and a thorough knowledge of JavaScript. Keep practicing and you’ll come up with these kind of answers naturally in time.

ADDENDUM

A previous version of this article incorrectly identified the third solution as O(1). I has been updated to the right answer.