Union and Intersection of two Arrays

In this article, we will go through two ways of finding union and two ways of finding intersection of arrays. But before that, let's take a look at what exactly is union and intersection of two arrays.

• Union of two arrays will contain all the elements from both arrays but the common elements won't repeat. Check out this example:

  

• Intersection of two arrays will have just the common elements of the two arrays.

  

Hope this gives you an idea about the kind of result we are expecting. Time to discuss the code!

Union

Iterative Approach

I am not sure if I should call this the iterative approach as both of the approaches use loops. But since the other one will be using a hash map, we can call this one iterative.

We begin by sorting our input arrays. And then we initialize two pointers i and j as starting indexes of the two arrays along with an empty array to store the resultant array.

Now we compare the elements at arr1[i] and arr2[j]. Since 1 is less than 3, we can push it to our union array and move i to the next element.

Again, 2 is less than 3 so we add it to union array and move to the next element.

Both arr[i] and arr[j] are have the 3. In this case, we add value from either one of the two arrays and increment both pointers.

This step would be repeated for 4 and 5 as well.

Let's take a look at our arrays real quick. We have exhausted the elements of arr1 and arr2 still has some elements left. Since it is a union between two arrays, we need to add any leftover elements to our result.

Here is the code for this approach:

function iter_union(arr1, arr2) {
  let res = [];
  let i = 0;
  let j = 0;
  let n = arr1.length;
  let m = arr2.length;
  // sorting the arrays
  arr1.sort();
  arr2.sort();
  while (i < n && j < m) {
    if (arr1[i] === arr2[j]) {
      res.push(arr1[i]);
      i++;
      j++;
    } else if (arr1[i] < arr2[j]) {
      res.push(arr1[i]);
      i++;
    } else {
      res.push(arr2[j]);
      j++;
    }
  }
  // pushing all the leftover elements
  while (i < n) {
    res.push(arr1[i++]);
  }
  while (j < m) {
    res.push(arr2[j++]);
  }

  return res;
}

iter_union([1, 2, 3, 4, 5], [3, 4, 5, 6, 7])
-> [1, 2, 3, 4, 5, 6, 7]

Hash Map Approach

We can get the union by using hash maps as well. I will be using JavaScript objects for this solution.

So the plan is quite simple. We will store all the elements of both arrays in a hash map or JS object. And the cool thing about JS objects is that the keys are always unique. See where I am going with this? We can get all the keys of our object in an array using Object.keys() method in JavaScript which would be our resultant union.

function hmap_union(arr1, arr2) {
  let hmap = {};
  arr1.forEach((element) => {
    // I stored the value as element itself
    hmap[element] = element;
  });
  arr2.forEach((element) => {
    hmap[element] = element;
  });
  // for arr1 = [1,2,3,4,5]
  // and arr2 = [3,4,5,6,7]
  // hmap = {
  //   1: 1,
  //   2: 2,
  //   3: 3,
  //   4: 4,
  //   5: 5,
  //   6: 6,
  //   7: 7,
  // };
  return Object.keys(hmap);
}

hmap_union([1, 2, 3, 4, 5], [3, 4, 5, 6, 7])
-> ['1', '2', '3', '4', '5', '6', '7']

This syntax might look alien to some. I would recommend you try implementing this in the language of your choice. Even in JS, you can use Set instead of Object.

Intersection

Iterative Approach

So finding the intersection of two arrays is similar to finding the union. But we only push the elements when they are equal. Take a look at the code to see the difference.

function iter_intersection(arr1, arr2) {
  let res = [];
  let i = 0;
  let j = 0;
  let n = arr1.length;
  let m = arr2.length; 

  arr1.sort();
  arr2.sort();
  while (i < n && j < m) {
    // move the pointer with smaller value to 
    // the next element
    if (arr1[i] > arr2[j]) {
      j++;
    } else if (arr1[i] < arr2[j]) {
      i++;
    } else {
      // push on the two elements when 
      // arr1[i] = arr2[j]
      res.push(arr1[i]);
      i++;
      j++;
    }
  }
  // no need to push the leftover elements here
  return res;
}

iter_intersection([1, 2, 3, 4, 5], [3, 4, 5, 6, 7])
-> [ 3, 4, 5 ]

Hash Map Approach

This one is probably the coolest of all codes we discussed today. I will again use JS object with all the alien methods that JS has to offer. You can understand the logic and implement it in your style.

We start by storing all the elements into the object with the element as the key and a default value false. This would mean that the element is not part of the intersection for now.

arr1 = [1, 2, 3, 4, 5]
hmap = {
  1: false,
  2: false,
  3: false,
  4: false,
  5: false,
};

Next, we iterate over the second array and for each element in the second array, we check if it already exists in hmap. If the element exists, we change the value of the element to true in our hash map.

Our object would end up looking like this by the end of this process:

arr2 = [3, 4, 5, 6, 7]
hmap = {
  1: false,
  2: false,
  3: true,
  4: true,
  5: true,
};

As you can see the keys with the value true is our answer. Here is my implementation of this approach.

function hmap_intersection(arr1, arr2) {
  let hmap = arr1.reduce((acc, curr) => {
    return { ...acc, [curr]: false };
  }, {});
  for (let x of arr2) {
    if (hmap[x] === false) {
      hmap[x] = true;
    }
  }
  return Object.entries(hmap)
    .filter(([key, value]) => value)
    .map(([key, value]) => {
      return +key;
    });
}

iter_intersection([1, 2, 3, 4, 5], [3, 4, 5, 6, 7])
-> [ 3, 4, 5 ]

This is it for this post. Hope you had fun. I will meet you in the next article where we will cyclically rotate an array by one.