How to [merge, intersect, diff] arrays in JavaScript
Tags: javascript, algorithms
Published: 2020-05-19 12:18:01

### Merge

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

```javascript
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!

```javascript
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?

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

`Native` means that this function is provided by the browser or server. `V8` engine uses [TimSort](https://v8.dev/blog/array-sort#timsort), for example. TimSort is a stable algorithm with `O(N * logN)` average complexity. But let's try to decrease the complexity.

```javascript
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.

```javascript
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:

```javascript
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!

```javascript
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.

```javascript
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;  
}
```