Visualized Algorithm Challenge 2: Finding the Difference Between Two Arrays

This is part 2 of an occasional series about visual explanations of algorithms in JavaScript. This scenario was originally used in the “Intermediate Algorithms” section of FreeCodeCamp.

When someone presents a programming challenge to you, do you use a system to break down the problem?

Let’s use an example. Here’s a challenge from FreeCodeCamp:

“Compare two arrays and return a new array with any items only found in one of the two given arrays, but not both. In other words, return the symmetric difference of the two arrays.”

Here are two example arrays:

[1, 2, 3, 5]
[1, 2, 3, 4, 5]

That is a terse explanation! But it is also clear in what the inputs and outputs should be.

If you are a beginner to intermediate JavaScript developer, your brain probably can’t break this into an algorithm immediately. But fortunately, you can create a mental model to break this down into smaller challenges.

In fact, this is one definition of expertise: the speed at which you can access and utilize a mental model to solve a problem.

In this explanation, we will focus on mental simulation: how to use motion and imagery to reveal one way to write the algorithm.

There will be three parts:

  1. Breaking the challenge down into multiple scenarios that you can imagine without code.
  2. Writing pseudocode in plain English
  3. Writing the actual code based on pseudocode.

Let’s get started!

Imagining The Building Blocks

Let’s quickly reframe the challenge. Here’s the original text:

“Compare two arrays and return a new array with any items only found in one of the two given arrays, but not both. In other words, return the symmetric difference of the two arrays.”

“Symmetric difference” is a term you might recognize from math class, so that is one clue. But here’s another: if you were able to combine these arrays into one larger array, then the challenge would be:

“Find all numbers that only appear once in the larger array.”

So, before moving onto pseudocode, I try to form a mental image of what will happen in the algorithm:

  1. There will be one big array
  2. We will need to iterate through that array and somehow determine which numbers appear once.
  3. We will return the numbers that only appear once in a final array.

I even go further to make sure I am imagining it in sufficient detail. I imagine a dog or person inspecting each number, and determining if it appears once.

Here’s an example of a different method: going through each array, and searching for matches in the other array.

In this example, you are searching for values in array 1 that match a value in array 2:

In the example above, the maginifying glass indicates which element in array 2 you should be searching for in array 1. The dog successfully finds three elements that also exist in array 2.

Here’s the opposite example: searching for values in array 2 that match a value from array 1.

In this case, all three values are found in the second array.

It is certainly possible to solve this problem by traversing through each individual array by searching the other. But that would force you to run the algorithm twice, which is harder to understand and does not take advantage of tools from ES6.

Writing Pseudocode in Plain English

This “algorithm” is really just a function that takes two arrays as inputs, and outputs a final array with just the values that occur once.

1- A function takes two arguments

Then, we need to combine those two into a single array.

1- A function takes two arguments

2- Combine them into one larger array

Then, we need to decide how to find the single values in that array. There are two options:

  1. Search each of the original arrays for that value, and stop when you have found the value in each array
  2. As you iterate through the larger array, choose one value and see if it occurs again.

Method 1 is a little more efficient because it does not require you to fully traverse through the larger array for every single value in the array. That would quickly become a memory-intensive process.

If there were 20 elements in the array, you would need to search through 19 elements upon every iteration through the array. That’s 361 elements!

Instead, here’s what we might do:

1- A function takes two arguments

2- Combine them into one larger array

3- For each element in the larger array, search for it in each of the smaller arrays.

4- Only keep the elements that appear once.

Here’s the visual version of that algorithm:

Now it’s time to turn that into code!

Writing the Code

First, we need a function that can take two inputs.

function findSingleValues(array1, array2){
}

findSingleValues([1, 2, 3], [1, 2, 3, 4, 5])

Then, we need to combine the two arrays into one using the concat() method.

function findSingleValues(array1, array2){
  let largeArray = array1.concat(array2);
}

findSingleValues([1, 2, 3], [1, 2, 3, 4, 5])

We need a way to select specific values from that array. We can use the filter() method to accomplish that.

function findSingleValues(array1, array2){
  let largeArray = array1.concat(array2);
  
  let singleVals = largeArray.filter( el => {
    // this is where we need to select single values
  })
}

findSingleValues([1, 2, 3], [1, 2, 3, 4, 5])

We store the results of the filter operation in the singleVals array.

Okay, here’s the hardest part. We need to write the logic that will ensure that an element only occurs in one of the two arrays.

That means we need an OR statement. We only want to keep elements that are included in one array BUT NOT the other.

We can use the includes() array method for that.

function findSingleValues(array1, array2){
  let largeArray = array1.concat(array2);
  
  let singleVals = largeArray.filter( el => {
    if ( !array1.includes(el) || !array2.includes(el) )
       return el;
  });

  return singleVals;
}

findSingleValues([1, 2, 3], [1, 2, 3, 4, 5])

In our example, only the values 4 and 5 are found in one array BUT NOT the other.

Here’s an interactive image of that block:

Interested In More Visual Tutorials?

If you would like to read more visual tutorials about HTML, CSS and JavaScript, check out the main CodeAnalogies site for 50+ tutorials.

Or, sign up here to get the latest.

Processing…
Success! You're on the list.

Leave a Reply