Seen set - Деконструкция реальности

Seen set — это множество уже увиденных элементов.

То есть структура данных, куда мы кладём элементы, которые уже встретили при
проходе по массиву, строке, графу, дереву или потоку событий.

Главная форма:

seen = set()

for x in arr:
    if x in seen:
        print("уже встречали")
    else:
        seen.add(x)

Допустим, есть массив:

[3, 5, 2, 5, 8]

Идём слева направо:

3 — не видели -> добавляем в seen
5 — не видели -> добавляем
2 — не видели -> добавляем
5 — уже есть в seen -> значит дубликат
8 — не видели -> добавляем

В итоге seen постепенно становится таким:

{}
{3}
{3, 5}
{3, 5, 2}
{3, 5, 2}      // второй 5 уже не добавляет ничего нового
{3, 5, 2, 8}

Чем seen set отличается от frequency map

Frequency map отвечает на вопрос:

сколько раз встретился элемент?

Пример:

5 -> 2
3 -> 1
2 -> 1
8 -> 1

А seen set отвечает только на вопрос:

видели мы этот элемент раньше или нет?

Пример:

seen = {3, 5, 2, 8}

То есть seen set не хранит количество. Он хранит только факт присутствия.

Интуитивно:

seen set      : элемент -> уже был / ещё не был
frequency map : элемент -> сколько раз был

1. Найти первый дубликат

def first_duplicate(nums):
    seen = set()

    for x in nums:
        if x in seen:
            return x

        seen.add(x)

    return None

Для массива:

[3, 5, 2, 5, 8]

результат:

2. Проверить, есть ли повторяющиеся элементы

На Java:

Set<Integer> seen = new HashSet<>();

for (int num : nums) {
    if (seen.contains(num)) {
        return true;
    }

    seen.add(num);
}

return false;

Это классический паттерн для задач типа:

contains duplicate

3. Не заходить повторно в узлы графа

В графах seen часто называют visited.

seen = set()

def dfs(node):
    if node in seen:
        return

    seen.add(node)

    for neighbor in graph[node]:
        dfs(neighbor)

Смысл: если уже были в этом узле, второй раз туда не идём. Иначе в графе с
циклами можно попасть в бесконечный обход.

4. Найти пересечение двух массивов

Если нужно быстро проверять, встречался ли элемент в первом массиве, можно
положить первый массив в set.

const a = [1, 2, 3, 4];
const b = [3, 4, 5, 6];

const seen = new Set(a);
const intersection = [];

for (const x of b) {
  if (seen.has(x)) {
    intersection.push(x);
  }
}

console.log(intersection); // [3, 4]

Когда выбирать seen set, а когда frequency map

Если нужно только понять, встречался элемент раньше или нет, бери
seen set.

Если нужно знать, сколько раз он встречался, бери frequency map.

Примеры:

Есть ли дубликаты?                     -> seen set
Сколько раз каждый элемент встречается? -> frequency map
Какая буква самая частая?               -> frequency map
Были ли мы уже в этом узле графа?       -> seen set

Сложность

Обычно операции add, has или contains в hash set работают за O(1) в
среднем.

Для прохода по массиву:

Time:  O(n)
Space: O(k)

где n — количество элементов, а k — количество уникальных элементов, которые
попали в seen.

Главная идея

seen set — это один из самых базовых и полезных алгоритмических приёмов.

Он заменяет постоянное сканирование массива вопросом:

лежит ли это уже в hash set?

Поэтому часто переводит решение из O(n^2) в O(n).