Оптимизация алгоритма пересечения (intersection) двух массивов или списков зависит от исходной реализации и требований.

Типичные подходы:

Использование множества (Set)

Если исходный алгоритм — вложенные циклы (O(n*m)), можно значительно ускорить, преобразовав один из списков в множество для быстрого поиска (O(1) в среднем):

function intersection(arr1, arr2) {
  const set2 = new Set(arr2);
  return arr1.filter(item => set2.has(item));
}

Сортировка и двухуказательный метод

Если данные отсортированы или можно их отсортировать, можно пройтись двумя указателями по обоим массивам, что даст O(n log n + m log m) из-за сортировки, но O(n + m) после:

function intersectionSorted(arr1, arr2) {
  arr1.sort();
  arr2.sort();
  let i = 0, j = 0;
  const result = [];
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] === arr2[j]) {
      result.push(arr1[i]);
      i++; j++;
    } else if (arr1[i] < arr2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return result;
}

Учитывать специфику данных

Если данные очень большие, можно использовать более сложные структуры или параллелизм.

В целом, использование множества — самый простой и эффективный способ для большинства случаев.

Как можно оптимизировать алгоритм intersection?