Хеш-множество / словарь

O(n)

Меняем память на скорость: множество отвечает "видел ли я это" за O(1), словарь считает "сколько каждого" за один проход по неотсортированным данным.

Сигналы

встречалось ли это раньшепосчитать сколько каждогонайти дубликатыесть ли подходящее/дополняющее значениеданные в любом порядке / не отсортированы

Шаблон

function firstDuplicate(arr) {
    const seen = new Set();
    for (const x of arr) {
        if (seen.has(x)) return x;
        seen.add(x);
    }
    return null;
}

Похоже, но не то

Два указателя (с концов): Два указателя требуют отсортированного массива и дают O(1) память. Если данные не отсортированы и сортировать нельзя, хеш даёт ответ за O(n).
Скользящее окно: Окно отвечает на вопрос про непрерывный отрезок. Простое множество/словарь отвечает про принадлежность или частоту по всей коллекции, без понятия отрезка.

не отсортировано, n до 1e5..1e6, один вопрос про принадлежность/частоту -> O(n) время, O(n) память. Сюда указывает именно то, что сортировка исключена.

Изучить этот паттерн