Algorithms 101: Find the Difference between Two Arrays in JavaScript

Noob. v. Algorithms #23, a custom, speedy method for finding the difference in two arrays

Joan Indiana Lyness
Nov 20 · 5 min read
difference between two arrays in red, image from Wikipedia

Today’s challenge from LeetCode is Find All Disappeared Numbers in Array.

Brute force

Our inputs include an actual array with missing numbers. We want to compare that array to an array of the same length, where there are no missing numbers. So if we are given [4,3,2,7,8,2,3,1], we want to compare it [1,2,3,4,5,6,7,8].

One way to make that comparison is to generate the array with no missing numbers. We can do this with Array.keys (MDN documentation here).

Here’s how that works:

Notice that you can use .slice(index) to return all elements starting with the index you pass in as an argument.

In our code, we can use these concepts like so:

Now, we can use JavaScript’s .filter() to compare the two:

On line 3, we’re asking asking for a return value of only those numbers in allNums that are not included in nums.

This approach works, but it is SLOOOOWWW.

Swapping out .indexOf() for includes does not make much of a difference:

We need a new approach!

There are a million solutions on LeetCode — I was looking for one that was efficient and easy to understand for a Noob like me. I found a great one by LeetCode’s Ashotovich1990.

It’s easiest to explain the concept first. Then we’ll move on to building the code. Here’s how he solved the problem:

Setup

Set up a comparison array of the correct length where all the values are false. If your input is [1,2,2], your comparison array will be [false, false, false].

First loop

Loop through the input array, amending the comparison array like so (to be explained later, below).

input array:                               [  1  ,   2   ,   2   ]comparison array before loop:              [false, false , false ]comparison array after loop:               [ true , true , false ]

Second Loop

Loop through the amended comparison array. When you find false , grab its index and add 1 to determine the value of the missing number.

comparison array after loop:               [ true , true , false ]indices =>                                     0   ,   1  ,   2missing number = index of false + 1                           3

Finally, push each missing number into a response array and return the response.

Building our solution

First, let’s set up an empty array called missing. We’ll use that to collect our missing numbers. (Noobs: you will often see this array named res, which is short for response. I prefer to use more semantic names).

Step 1, setting up the comparison array

Let’s set up our comparison array, using JavaScript’s .fill(). Here’s how that works for setting up new arrays. (You can also use it to overwrite values of an existing array. MDN documentation here).

In the code below, we save our comparison array as seen. We start out with all the values set to false to show that we have not yet ‘seen’ any of the numbers from our input array.

Step 2, our first loop. Change appropriate values in ‘seen’ to true.

let nums = [1,2,2]
//seen = [false, false, false]
for (let i = 0; i < nums.length; i++) {
seen[nums[i]-1] = true;
};

Let’s unpack that. We are looping through our input array, nums. We’re checking the value at each nums[i], subtracting one, and then changing the value at the same index of seen to equal true.

If this is confusing to you, you’re not alone. Using the above inputs, here is how seen evolves after each loop:

let nums = [1,2,2]
seen = [false, false, false]
seen[nums[i]-1] = true;
loop 1, i = 0:
seen[nums[0] - 1]
=> nums[0] = 1
=> seen[1 - 1]
=> seen[0] = true
seen => [true, false, false]
loop 2, i = 1:
seen[nums[1] - 1]
=> nums[1] = 2
=> seen[2 - 1]
=> seen[1] = true
seen => [true, true, false]
loop 3, i = 3:
seen[nums[3] - 1]
=> nums[2] = 2
=> seen[2 - 1]
=> seen[1] = true
seen => [true, true, false]

Our code so far:

Step 3. Our second loop.

Here’s where we loop through seen, looking for values of false.

1.  for (let i = 0; i < seen.length; i++) {
2. if (!seen[i]){
3. missing.push(i+1);
4. };

On line 2, seen[i] is the current item we’re looping over. When we write if(!seen[i]), we’re saying, if the current item evaluates to false (continue to line 3).

On line 3, we’re adding 1 to the index number to get the value of the missing number, and pushing that number into our missing array.

Here’s the final code.

Thank you Ashotovich1990!

It’s not great for memory, but it is great for speed!

You can see the code execute live here on PythonTutor.com and you can play with it here on repl.it:

https://repl.it/@Joan_IndianaInd/missing-numbers-in-array

Copyright © Joan Indiana Lyness 2019

In case you missed it: Algorithms 101: Rotate Array in JavaScript — three solutions

JavaScript in Plain English

Learn the web's most important programming language.

Joan Indiana Lyness

Written by

Hire me in Washington DC! Full-stack developer, Ruby, Rails, JavaScript, i love! React. My portfolio: https://joan-indiana-lyness.com/projects

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade