2657. Find the Prefix Common Array of Two Arrays — разбор задачи

1. Условие задачи

Дано: две перестановки A и B длины n. Это значит, что каждый массив содержит все числа от 1 до n ровно по одному разу, просто, возможно, в разном порядке.

Нужно: построить массив C, где C[i] — количество чисел, которые встретились и в префиксе A[0:i+1], и в префиксе B[0:i+1].

Иными словами, для каждой позиции i смотрим на начала обоих массивов до этой позиции включительно и считаем, сколько чисел встретилось в обоих префиксах.

Например:

A = [1, 3, 2, 4]
B = [3, 1, 2, 4]

при i = 0 префиксы [1] и [3], общих чисел нет;
при i = 1 префиксы [1, 3] и [3, 1], общие числа — 1 и 3;
при i = 2 добавляется общее число 2;
при i = 3 добавляется общее число 4.

Ответ: [0, 2, 3, 4].

Ограничения небольшие: 1 <= n <= 50. Но важнее другое: по условию A и B — именно перестановки, поэтому внутри одного массива одинаковые числа не повторяются. На этой гарантии основано самое короткое решение.

2. Решение

Решение в лоб

Будем идти по массивам слева направо и постепенно собирать два множества: числа из уже пройденной части A и числа из уже пройденной части B.

После добавления очередной пары чисел пересекаем множества и записываем количество общих элементов:

class Solution:
    def findThePrefixCommonArray(
        self,
        A: list[int],
        B: list[int],
    ) -> list[int]:
        seen_a = set()
        seen_b = set()
        answer = []

        for a, b in zip(A, B):
            seen_a.add(a)
            seen_b.add(b)
            answer.append(len(seen_a & seen_b))

        return answer

Добавление в множество работает за O(1) в среднем. Но само пересечение на каждом шаге может просматривать до O(N) элементов. Поскольку мы считаем его N раз, суммарно получаем O(N^2) времени и O(N) дополнительной памяти.

Такое решение проходит при n <= 50, но каждый раз заново ищет все общие числа. На собеседовании от него удобно перейти к линейному решению: не пересчитывать весь результат, а обновлять счётчик только по двум новым элементам.

Основная идея: два множества и счётчик

Будем идти по массивам слева направо и хранить:

seen_a — числа, которые уже встретились в A;
seen_b — числа, которые уже встретились в B;
common_count — сколько разных чисел уже встретилось в обоих массивах.

Когда берём очередное число a из массива A, возможны два случая:

a уже есть в seen_a — раньше мы его обрабатывали, поэтому ничего не меняется;
a встретилось в A впервые — добавляем его в seen_a и проверяем, было ли оно раньше в B. Если было, число только сейчас стало общим, поэтому увеличиваем common_count.

Затем точно так же обрабатываем очередное число b из массива B.

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

Алгоритм по шагам

Создаём пустые множества seen_a и seen_b.
Заводим счётчик common_count = 0.
Идём по массивам слева направо.
Если новое число из A раньше не встречалось в A, добавляем его в seen_a. Если оно уже есть в seen_b, увеличиваем счётчик.
Симметрично обрабатываем новое число из B.
Добавляем текущее значение common_count в ответ.

Визуализация на `A = [1, 3, 2, 4]`, `B = [3, 1, 2, 4]`

i	A[i]	B[i]	Что произошло	common_count
0	1	3	оба числа увидели впервые, общих пока нет	0
1	3	1	`3` уже было в `B`, а `1` уже было в `A`	2
2	2	2	при обработке `B[i]` двойка уже находится в `seen_a`	3
3	4	4	аналогично четвёрка становится общей	4

Главный инвариант: после обработки позиции i в common_count записано количество разных чисел, которые уже появились и в seen_a, и в seen_b.

Код на Python

class Solution:
    def findThePrefixCommonArray(
        self,
        A: list[int],
        B: list[int],
    ) -> list[int]:
        seen_a = set()
        seen_b = set()
        common_count = 0
        answer = []

        for a, b in zip(A, B):
            # Число a впервые появилось в A
            if a not in seen_a:
                seen_a.add(a)
                if a in seen_b:
                    common_count += 1

            # Число b впервые появилось в B
            if b not in seen_b:
                seen_b.add(b)
                if b in seen_a:
                    common_count += 1

            answer.append(common_count)

        return answer

Краевые случаи

n == 1 — единственное число совпадает, поэтому ответ [1].
A[i] == B[i] — при обработке числа из B оно уже находится в seen_a, поэтому счётчик увеличивается ровно один раз.
Массивы полностью совпадают — ответ будет [1, 2, ..., n].
Первые элементы долго идут в разном порядке — несколько первых значений ответа могут быть нулями.
Последнее значение всегда равно n, потому что полные массивы содержат один и тот же набор чисел.

3. Сложность алгоритма

Мы один раз проходим по массивам. В среднем проверка наличия числа в множестве и добавление в него работают за O(1).

Итог по времени: O(N) в среднем.

В двух множествах хранится не больше O(N) разных чисел.

Итог по дополнительной памяти: O(N) без учёта возвращаемого массива.

4. Вариация Яндекса: произвольные массивы с дубликатами

На собеседовании условие могут изменить:

Даны два массива одинаковой длины. Значения в них могут повторяться, а наборы уникальных значений могут не совпадать. Для каждого i нужно найти количество различных чисел, которые встретились в обоих префиксах. Повторные вхождения одного и того же числа ответ не увеличивают.

Например:

A = [1, 1, 2, 5, 2]
B = [2, 1, 2, 3, 5]

Тогда ответ равен [0, 1, 2, 2, 3]:

i	Префикс A	Префикс B	Общие разные числа	Ответ
0	`[1]`	`[2]`	общих чисел нет	0
1	`[1, 1]`	`[2, 1]`	только `1`	1
2	`[1, 1, 2]`	`[2, 1, 2]`	`1` и `2`	2
3	`[1, 1, 2, 5]`	`[2, 1, 2, 3]`	по-прежнему `1` и `2`	2
4	`[1, 1, 2, 5, 2]`	`[2, 1, 2, 3, 5]`	добавилось число `5`	3

Для этой вариации не нужен другой алгоритм. Основное решение с двумя множествами уже учитывает все дополнительные условия:

повторное появление числа в A игнорируется, потому что оно уже есть в seen_a;
повторное появление числа в B игнорируется по той же причине;
число, которое встречается только в одном массиве, не увеличивает счётчик;
разные наборы уникальных значений не создают никаких проблем.

Именно поэтому решение с двумя множествами удобно показывать как основное: оно достаточно простое, работает за один проход и не зависит от того, являются ли массивы перестановками.

Краевые случаи вариации

Все элементы одинаковые в обоих массивах — после первого шага ответ всегда равен 1.
Число много раз встречается только в одном массиве — оно никогда не увеличивает ответ.
Наборы уникальных значений не пересекаются — ответ состоит из нулей.
A[i] == B[i], и число встречается впервые — ответ увеличивается ровно на 1.
A[i] == B[i], но число уже встречалось в обоих префиксах — ответ не меняется.
Значение раньше было только в B, а теперь впервые появилось в A — ответ увеличивается на 1, и симметричный случай работает так же.

Сложность не меняется: O(N) времени в среднем и O(N) дополнительной памяти.

5. Дополнительный трюк для оригинальной задачи: массив частот

Если на собеседовании попросят решить оригинальную задачу без set или другой хеш-таблицы, можно воспользоваться строгими гарантиями LeetCode:

каждый массив содержит числа только от 1 до n;
внутри одного массива числа не повторяются;
оба массива содержат одинаковый набор чисел.

Заведём один массив frequency длины n + 1. Для каждого числа будем считать, сколько раз оно встретилось при совместном проходе по A и B.

Из-за отсутствия дубликатов частота 2 может означать только одно: число один раз встретилось в A и один раз в B. В этот момент оно становится общим, и мы увеличиваем ответ.

class Solution:
    def findThePrefixCommonArray(
        self,
        A: list[int],
        B: list[int],
    ) -> list[int]:
        n = len(A)
        frequency = [0] * (n + 1)
        common_count = 0
        answer = []

        for i in range(n):
            frequency[A[i]] += 1
            if frequency[A[i]] == 2:
                common_count += 1

            frequency[B[i]] += 1
            if frequency[B[i]] == 2:
                common_count += 1

            answer.append(common_count)

        return answer

Это решение тоже работает за O(N) времени и использует O(N) дополнительной памяти. Формально памяти не стало меньше, но здесь нет хеширования: мы обращаемся к ячейке массива напрямую по значению числа.

Этот трюк нельзя без изменений переносить на вариацию Яндекса. Например, если A = [7, 7], а B = [1, 2], общая частота семёрки станет равна 2, хотя в массиве B её вообще нет. Поэтому решение с частотами оставляем как красивую оптимизацию именно для оригинального условия.

6. Вывод

Основное решение задачи — два множества и счётчик общих чисел. Мы увеличиваем счётчик только тогда, когда число впервые появляется в одном массиве, а в другом уже встречалось. Решение работает за один проход и подходит как для оригинальных перестановок, так и для вариации Яндекса с дубликатами.

Массив частот — дополнительный трюк для строгого условия LeetCode. Он позволяет отказаться от хеш-таблиц, но опирается на уникальность чисел внутри каждого массива и известный диапазон значений.

Материал подготовлен по условию LeetCode, официальному Editorial и лучшим пользовательским Solutions, отсортированным по Most Votes.

🐆