Какая сложность алгоритма нахождения пересечения двух массивов

Наивное решение с вложенными циклами имеет сложность O(n*m), где n и m — длины массивов.

Оптимальное решение с использованием хэш-таблицы (Set):

1. Создаем Set из первого массива — O(n)
2. Фильтруем второй массив, оставляя элементы из Set — O(m)
3. Общая сложность — O(n + m)

Пример:

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

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