Compare two arrays and find common elements

compare-and-find-common-element.ts

/*
Given two arrays of elements, say 1 and 2, write a function that finds the 
common elements between them and returns the following three arrays:
- An array containing all elements in 1 that aren't also contained in 2.
- An array containing all common elements that are both in 1 and 2.
- An array containing all elements in 2 that aren't also contained in 1.

*/

// Simple solution - O(n^2)
const compare = (array1, array2) => {
  const result1 = array1.filter((element) => array2.indexOf(element) === -1);

  const result2 = array1.filter((element) => array2.indexOf(element) !== -1);

  const result3 = array2.filter((element) => array1.indexOf(element) === -1);

  return [result1, result2, result3];
};

// Performant solution, using hashmaps
const compare2 = <A>(
  array1: Array<A>,
  array2: Array<A>
): [Array<A>, Array<A>, Array<A>] => {
  let dict = new Map<A, Array<number>>();
  array1.forEach((el) => {
    dict.set(el, [1]);
  });
  array2.forEach((el) => {
    const arr = dict.get(el) ?? [];
    dict.set(el, arr.concat([2]));
  });
  let result1: Array<A> = [];
  let result2: Array<A> = [];
  let result3: Array<A> = [];

  Array.from(dict.keys()).forEach((element: A) => {
    const inArrays = dict.get(element);

    if (inArrays.indexOf(1) === -1) {
      result3.push(element);
    }
    if (inArrays.indexOf(2) === -1) {
      result1.push(element);
    }
    if (inArrays.length == 2) {
      result2.push(element);
    }
  });
  return [result1, result2, result3];
};

// Performant solution, using list sorting
const compare3 = (
  array1: Array<number>,
  array2: Array<number>
): [Array<number>, Array<number>, Array<number>] => {
  const [array1Sorted, array2Sorted] = [array1.sort(), array2.sort()];
  const result1 = [];
  const result2 = [];
  const result3 = [];
  while (array1Sorted.length > 0 || array2Sorted.length > 0) {
    const el1 = array1Sorted[0];
    const el2 = array2Sorted[0];
    if (el1 < el2 || el2 === undefined) {
      result1.push(array1Sorted.shift());
    } else if (el1 > el2 || el1 === undefined) {
      result3.push(array2Sorted.shift());
    } else if (el1 === el2) {
      result2.push(array1Sorted.shift());
      array2Sorted.shift();
    } else {
      throw new Error("Function only works with comparable objects");
    }
  }
  return [result1, result2, result3];
};

const array1 = [1, 2, 3, 4];
const array2 = [0, 1, 2];

console.log(compare(array1, array2), "=", [[3, 4], [1, 2], [0]]);
console.log(compare2(array1, array2), "=", [[3, 4], [1, 2], [0]]);
console.log(compare3(array1, array2), "=", [[3, 4], [1, 2], [0]]);