How to [merge, intersect, diff] arrays in JavaScript

Merge

How to combine two sorted arrays into one? We can do this easily with the spread operator.

a1 = [1, 2, 5, 6, 9];
a2 = [3, 4, 7, 8, 10];

res = [...a1, ...a2]; // [1, 2, 5, 6, 9, 3, 4, 7, 8, 10]

But if we want to combine and sort? Again, nothing complicated!

res = [...a1, ...a2].sort((a, b) => +a > +b); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

What is the cost of this solution? The most difficult part in this case is sorting. How is this method implemented in JavaScript?

[].sort.toString() // "function sort() { [native code] }"

Native means that this function is provided by the browser or server. V8 engine uses TimSort, for example. TimSort is a stable algorithm with O(N * logN) average complexity. But let's try to decrease the complexity.

function merge(a1, a2) {
  const a1Len = a1.length;
  const a2Len = a2.length;

  const res = [];

  for (let i = 0, j = 0, k = 0; k < a1Len + a2Len; ++k) {
    if (i === a1Len) {
      res[k] = a2[j++];
      continue;
    }

    if (j === a2Len) {
      res[k] = a1[i++];
      continue;
    }

    if (a1[i] >= a2[j]) {
      res[k] = a2[j++];
    } else {
      res[k] = a1[i++];
    }      
  }

  return res;
}

Now we have reduced complexity and combined merging and sorting in one step. The logic of this algorithm is easy to understand and I will not explain it.

Intersect

The goal is to get the intersection of two arrays. The resulting array will contain only those elements from the arrays a1 and a2 that are included in both arrays. No duplicates of course.

a1 = [1,2,3,5,6,6,9];
a2 = [3,4,5,6,6,7,8,10];

res = [...new Set(a1.filter(i => a2.includes(i)))] // [3, 5, 6]

This is the first thing that occurred to me. Filter the elements of the a1 array and get rid of duplicates with Set. But there is a more interesting solution:

function intersect(a1, a2) {
  const a1Len = a1.length;
  const a2Len = a2.length;

  const res = [];

  for (let i = 0, index = 0; i < a1Len; i++) {
    let j = 0;
    let k = 0;

    while (a2[j] !== a1[i] && j < a2Len) {
      j++;
    }

    while (res[k] !== a1[i] && k < index) {
      k++;
    }

    if (j !== a2Len && k === index) {
      res[index++] = a1[i];
    }
  }

  return res;
}

Difference

The difference of arrays a1 и a2 is an array that contains those elements from the a1 array that are not in the a2 array. Let's do it!

a1 = [6,1,2,3,5,6,6,9];
a2 = [6,3,4,5,6,6,7,8,10];

res = [...new Set(a.filter(i => !b.includes(i)))]; // [1, 2, 9]

Very easy! Let's do it differently.

function diff(a1, a2) {
  const a1Len = a1.length;
  const a2Len = a2.length;

  const res = [];

  for (let i = 0, index = 0; i < a1Len; i++) {
    let j = 0;
    let k = 0;

    while(a2[j] !== a1[i] && j < a2Len) {
      j++;
    }

    while(res[k] !== a1[i] && k < index) {
      k++;
    }

    if (j === a2Len && k === index) {
      res[index++] = a1[i];
    }
  }

  return res;  
}

Blog

How to [merge, intersect, diff] arrays in JavaScript

Victor Magarlamov

Merge

Intersect

Difference

Join Our Newsletter. No Spam, Only the good stuff.

Related