intersectionWith

intersectionWith.js

// - Time: O(n^2 + ∑ |tail[i]|)
// - Space: O(n)
export default function intersectionWith(comparator, ...arrays) {
  if (arrays == null || arrays.length === 0) {
    return [];
  }

  const [head, ...tail] = arrays;
  let intersections = [];

  for (const val of head) {
    // skip duplicates in head
    if (!intersections.some((c) => comparator(val, c))) {
      intersections.push(val);
    }
  }

  for (const array of tail) {
    // short circuit if intersections are empty
    if (intersections.length === 0) {
      return [];
    }

    if (intersections.length <= array.length) {
      intersections = intersections.filter((val) =>
        array.some((v) => comparator(val, v)),
      );
    } else {
      const matchedIndices = new Set();

      for (const val of array) {
        for (let i = 0; i < intersections.length; i += 1) {
          if (comparator(val, intersections[i])) {
            matchedIndices.add(i);
            break;
          }
        }
      }

      intersections = intersections.filter((_, i) => matchedIndices.has(i));
    }
  }

  return intersections;
}