Finding the Intersection of Two Arrays

Today's algorithm is the Intersection of Two Arrays problem:

Given two arrays, write a function to compute their intersection.

Each element in the result has to be unique, and the result can be in any order.

For example, if the two arrays were [3, 5, 3, 2] and [3, 5, 3], the output should be [3, 5], because those are the two unique elements found in both arrays.

This problem is a good instance to make use of sets. A set is an object of unique values, and are particularly useful in problems where you're told to return unique elements. You can learn more about sets here.

In this post, I'll be discussing how I want to approach this problem, then coding the solution in JavaScript.

Approaching the Problem

In this problem, we're given two arrays, which may both have repeating numbers in them, and we only want to return unique, shared values. One way to solve this is by turning the first array into a set, which will remove any duplicate values.

Turning an array into a set is actually a very short process. Let's say you had an array called arr1, which was equal to [2, 4, 4], and wanted to create a set based on that array:

  const set1 = new Set(arr1)

Based on the above statement, set1 will equal {2, 4}.

Once we turn the first given array into a set, we can then go through each element of the second given array, and check if it's in the set. If it is, we'll add it to a result array, which we'll return at the end. We'll also want to remove that element from the set, so that if the second array has a duplicate value, we don't add it to the result array twice.

To check if a set has an element, we can use the has() method, which returns a boolean value (true or false). For example, if we're still working with set1 from above:

  const arr1 = [2, 4, 4]
  const set1 = new Set(arr1) // {2, 4}
  set1.has(2) // will return true
  set1.has(5) // will return false

To remove an element from a set, we can use the delete() method, which removes a specific element from a set. To continue with the same example:

  const arr1 = [2, 4, 4]
  const set1 = new Set(arr1) // {2, 4}
  set1.delete(2) // set1 = {4}

Coding the Solution

With the above methods in mind, we can start out by creating a new set based on nums1, which is the first inputted array. We can do this by setting a new variable called set equal to new Set(nums1).

We also can create a new array called result, which we'll start as an empty array. This array will be returned at the end of the function, so we can include the result statement now.

function intersection2(nums1, nums2) {
  let set = new Set(nums1);
  let result = [];
  //...
  return result;
}

Now, we'll want to check each value of nums2 to see if it's in set. To do this, we can set up a for loop, which will iterate through each value of nums2, and therefore will go from 0 until the length of the nums2 array.

function intersection2(nums1, nums2) {
  let set = new Set(nums1);
  let result = [];
  for (let i = 0; i < nums2.length; i++) {
    //...
  }
  return result;
}

Inside the for loop, we'll want to check if the set has each element of nums2. Each element of nums2 is accessed with nums2[i]. We then can create a conditional statement to see if the set has that element, using set.has(nums2[i]).

If this returns true, then we'll want to do two things: first, we'll want to add the element to the result array, using .push(). We'll then want to delete that element from set, so that we don't add duplicate values to the result array.

function intersection2(nums1, nums2) {
  let set = new Set(nums1);
  let result = [];
  for (let i = 0; i < nums2.length; i++) {
    if (set.has(nums2[i])) {
      result.push(nums2[i]);
      set.delete(nums2[i]);
    }
  }
  return result;
}

This will return an array containing unique values shared by both arrays.

--

Let me know if you have any questions or alternate solutions to finding the intersection of two arrays.