Como se pode otimizar o algoritmo de interseção?

A otimização do algoritmo de interseção de dois arrays ou listas depende da implementação inicial e dos requisitos.

Abordagens típicas:

1. Uso de conjuntos (Set)

Se o algoritmo inicial consiste em ciclos aninhados (O(n*m)), pode ser significativamente acelerado convertendo uma das listas em um conjunto para buscas rápidas (O(1) em média):

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

2. Ordenação e método de dois ponteiros

Se os dados estiverem ordenados ou puderem ser ordenados, pode-se percorrer ambos os arrays com dois ponteiros, o que resulta em O(n log n + m log m) devido à ordenação, mas O(n + m) após:

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

3. Considerar a especificidade dos dados

Se os dados forem muito grandes, pode-se usar estruturas mais complexas ou paralelismo.

De modo geral, o uso de conjuntos é a forma mais simples e eficiente na maioria dos casos.