LeetCode Master: Алгоритмические паттерны и стратегии BigTech

Анализ сложности: Как Big-O определяет ваш оффер

Представьте ситуацию: вы на техническом собеседовании в Google. Вы только что написали код, который идеально решает задачу. Тестовые примеры проходят, логика безупречна. Вы выдыхаете, но интервьюер смотрит на доску и произносит самую частую фразу в BigTech: «Отлично. А можем ли мы сделать это быстрее?»

В этот момент проверяется не ваше знание языка программирования, а понимание масштабов. Код, который мгновенно обрабатывает 10 элементов, может повесить сервер, если элементов станет миллион. Чтобы не обсуждать скорость абстрактных серверов, инженеры используют универсальный язык — нотацию Big-O.

Big-O — это математический способ описать, как растут требования вашего алгоритма к времени и памяти при увеличении объема входных данных.

Время — это не секунды, а операции

Почему мы не измеряем алгоритмы в миллисекундах? Потому что миллисекунды зависят от процессора, загруженности ОС и языка программирования. Вместо этого мы считаем количество базовых операций (присваивание, сравнение, арифметическое действие) относительно размера входных данных, который мы обозначаем как $N$ .

Big-O всегда описывает худший сценарий (worst-case). Если ваш алгоритм ищет число в массиве и случайно находит его первым же элементом — это везение, а не показатель эффективности. Нас интересует, что произойдет, если искомого числа в массиве вообще нет, и алгоритму придется проверить каждый элемент.

Основные классы сложности (Time Complexity)

Давайте посмотрим, как выглядят самые частые оценки сложности в коде.

1. Константное время: $O(1)$ Время выполнения не зависит от размера данных. Доступ к элементу массива по индексу или проверка четности числа — это $O(1)$ .

def get_first_element(arr):
    return arr[0] # Всегда 1 операция, даже если в массиве миллиард чисел

2. Линейное время: $O(N)$ Количество операций растет пропорционально объему данных. Если данных в 10 раз больше, алгоритм работает в 10 раз дольше. Типичный маркер — один цикл по всем элементам.

def find_max(arr):
    max_val = arr[0]
    for num in arr: # Цикл выполнится N раз
        if num > max_val:
            max_val = num
    return max_val

3. Квадратичное время: $O(N^2)$ Время растет в квадрате от объема данных. Увеличили вход в 10 раз — время выросло в 100 раз. Это классические вложенные циклы. В BigTech квадратичных решений почти всегда стараются избегать.

def print_all_pairs(arr):
    for i in arr:           # Внешний цикл N раз
        for j in arr:       # Внутренний цикл N раз
            print(i, j)     # Итого N * N = N^2 операций

Главные правила Big-O: Искусство отбрасывать лишнее

При оценке алгоритма мы не занимаемся точной бухгалтерией. Нас интересует только тенденция роста при огромных $N$ . Поэтому существуют два железных правила упрощения.

Правило 1: Отбрасываем константы Если ваш алгоритм дважды проходит по массиву из $N$ элементов, математически это $O(2N)$ . Но в нотации Big-O константы игнорируются. $O(2N)$ превращается в $O(N)$ . Почему? Потому что при $N = 1 000 000$ разница между $N$ и $2N$ ничтожна по сравнению с разницей между $N$ и $N^2$ . График остается линейным.

Правило 2: Оставляем только доминирующий член Если алгоритм содержит несколько шагов с разной сложностью, итоговая сложность определяется самым медленным шагом. Допустим, ваш код сначала сортирует массив (обычно это $O(N \log N)$ ), а затем один раз проходит по нему циклом ( $O(N)$ ). Общая сложность — $O(N \log N + N)$ . Поскольку при больших $N$ значение $N \log N$ растет значительно быстрее, чем просто $N$ , меньшим слагаемым пренебрегают. Итог: $O(N \log N)$ .

Пространственная сложность (Space Complexity)

Big-O применяется не только к времени выполнения, но и к потребляемой памяти. Space Complexity показывает, сколько дополнительной памяти требует алгоритм.

Важно: память, занятая самими входными данными, обычно не учитывается. Мы считаем только ту память, которую алгоритм запрашивает в процессе работы (вспомогательные массивы, хеш-таблицы, стек вызовов при рекурсии).

Здесь возникает концепция In-place алгоритмов. Это алгоритмы, которые преобразуют данные прямо в исходной структуре, не требуя выделения новой памяти (их пространственная сложность $O(1)$ ).

Пример: Вам нужно перевернуть массив.

Плохой подход по памяти: создать новый пустой массив, пройтись по старому с конца и записать элементы в новый. Требует $O(N)$ дополнительной памяти.

In-place подход: использовать два указателя (в начале и в конце массива) и менять элементы местами, сдвигаясь к центру. Дополнительная память — только одна переменная для обмена. Это $O(1)$ .

Секретный чит-код LeetCode: Ограничения (Constraints)

Теперь самое важное для практики. На LeetCode и реальных собеседованиях в условии задачи всегда есть блок Constraints (Ограничения). Например: $1 \leq arr.length \leq 10^5$ .

Это не просто техническая деталь — это прямая подсказка, какую алгоритмическую сложность от вас ждут.

Современные серверы (и проверяющая система LeetCode) выполняют примерно $10^7 - 10^8$ простых операций в секунду. Если ваш алгоритм требует больше операций, вы получите ошибку Time Limit Exceeded (TLE).

Зная размер входа $N$ , вы можете заранее отсечь неподходящие подходы:

Ограничение $N$	Допустимая сложность	Ожидаемый подход
$N \leq 10$	$O(N!)$ , $O(2^N)$	Перебор всех вариантов (Бэктрекинг)
$N \leq 100$	$O(N^3)$	Тройные вложенные циклы, сложное ДП
$N \leq 10^4$	$O(N^2)$	Двойные циклы, матричные операции
$N \leq 10^5$	$O(N \log N)$ или $O(N)$	Сортировка, Хеш-таблицы, Два указателя
$N \geq 10^9$	$O(\log N)$ или $O(1)$	Бинарный поиск, Математическая формула

Если в задаче сказано, что длина массива может достигать $10^5$ , даже не пытайтесь писать решение с вложенными циклами $O(N^2)$ . Возведя $10^5$ в квадрат, вы получите $10^{10}$ операций — алгоритм будет работать несколько минут вместо положенной секунды. Вам нужен алгоритм за $O(N)$ или $O(N \log N)$ .

В следующих главах мы начнем разбирать конкретные паттерны — от «Двух указателей» до «Скользящего окна», — которые как раз и позволяют магическим образом превращать медленные квадратичные решения $O(N^2)$ в элегантные линейные $O(N)$ , обеспечивая вам тот самый заветный оффер.

Паттерн Two Pointers: Сжатие пространства поиска

В прошлой главе мы выяснили: если размер входных данных $N = 10^5$ , алгоритм со сложностью $O(N^2)$ совершит $10^{10}$ операций и гарантированно получит отказ системы (Time Limit Exceeded). Но что делать, если задача буквально просит найти пару элементов? Наивный подход всегда требует двух вложенных циклов.

Здесь на сцену выходит паттерн Two Pointers (Два указателя). Это не структура данных и не сложный математический трюк. Это стратегия обхода, которая позволяет сократить время поиска с $O(N^2)$ до $O(N)$ , сохраняя потребление памяти на идеальном уровне $O(1)$ (In-place).

Главный секрет этого паттерна — он не просто ищет ответ быстрее. Он позволяет безопасно отбрасывать огромные куски пространства поиска, даже не проверяя их.

Как работает сжатие пространства поиска

Представьте, что вам нужно найти двух человек в шеренге, чей суммарный рост равен ровно 350 см. Шеренга построена по росту (от низких к высоким).

Если использовать вложенные циклы, вы берете первого человека и по очереди примеряете к нему всех остальных. Затем берете второго и делаете то же самое. Это $O(N^2)$ .

Паттерн Two Pointers предлагает другой путь:

Ставим левый указатель (L) на самого низкого, а правый (R) — на самого высокого.
Складываем их рост.
Если сумма больше 350 см, то самый высокий человек в паре с самым низким уже дает перебор. Значит, этот высокий человек в паре с любым другим (кто еще выше первого) даст еще больший перебор. Мы можем смело сказать ему: «Вы нам не подходите, выходите из строя». Мы сдвигаем правый указатель влево.
Если сумма меньше 350 см, логика зеркальна: самый низкий человек даже в паре с самым высоким не дотягивает до цели. Сдвигаем левый указатель вправо.

Мы делаем ровно один проход по шеренге. Каждый шаг исключает одного человека из дальнейшего поиска.

Классика: Two Sum II

В терминах LeetCode эта задача называется Two Sum II - Input Array Is Sorted.

Пусть у нас есть отсортированный массив и цель (target): $A = [2, 7, 11, 15]$ , $target = 9$

Мы проверяем сумму на концах: $Sum = A[L] + A[R]$ .

Вместо того чтобы проверять все возможные пары (площадь треугольника на схеме выше), наши указатели двигаются по границе, отсекая целые строки и столбцы неверных вариантов. Мы сжали двумерное пространство поиска $O(N^2)$ до одномерного пути $O(N)$ .

Неочевидное применение: Container With Most Water

С отсортированными массивами логика понятна. Но Two Pointers работает и там, где явной сортировки нет, но есть монотонная зависимость.

Разберем задачу Container With Most Water (Контейнер с наибольшим количеством воды), которая часто встречается на собеседованиях в FAANG. Вам дан массив высот вертикальных линий. Нужно выбрать две линии так, чтобы вместе с осью X они образовали контейнер, вмещающий максимум воды.

Формула объема (площади) зависит от двух факторов — ширины и высоты: $Area = (R - L) \times \min(H[L], H[R])$ где $R - L$ — расстояние между линиями (ширина), а $\min(H[L], H[R])$ — высота более короткой линии (вода перельется через край, если налить выше).

Вложенные циклы снова дадут $O(N^2)$ . Как применить два указателя? Мы начинаем с самых краев массива. Почему? Потому что на старте у нас максимально возможная ширина.

Чтобы найти контейнер большего объема, нам придется сближать указатели (ширина будет уменьшаться). Единственный шанс компенсировать потерю ширины — найти более высокую линию.

Поэтому на каждом шаге мы смотрим на высоты под нашими указателями и сдвигаем тот указатель, чья линия ниже. Если $H[L] < H[R]$ , мы двигаем $L$ вправо. Почему? Потому что если мы сдвинем $R$ влево, ширина уменьшится, а высота контейнера все равно не сможет превысить $H[L]$ . Площадь гарантированно станет меньше. Сдвигая меньшую высоту, мы даем себе шанс найти линию выше и увеличить общую площадь.

Как распознать паттерн на интервью

Паттерн Two Pointers (встречное движение) — ваш главный кандидат на использование, если в задаче совпадают следующие условия:

Нужно найти пару, тройку или подмассив, удовлетворяющий определенному условию (сумма, разность, площадь).
Данные отсортированы или обладают свойством, где движение в одну сторону предсказуемо меняет результат (как ширина в задаче с контейнером).
Ограничения задачи требуют $O(N)$ (или $O(N \log N)$ , что намекает на необходимость сначала отсортировать массив, а затем применить два указателя).
Требуется In-place решение, то есть нельзя выделять память под хеш-таблицы или новые массивы (пространственная сложность $O(1)$ ).

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

Паттерн Sliding Window: Оптимизация вложенных циклов

Сжатие пространства поиска встречными указателями отлично работает, когда мы ищем пару элементов. Но что, если задача требует найти не два разрозненных элемента, а непрерывную последовательность — подмассив или подстроку? Если мы будем проверять каждую возможную последовательность, запуская цикл внутри цикла, сложность неизбежно улетит в $O(N^2)$ .

Чтобы остаться в рамках $O(N)$ , оба указателя должны двигаться в одном направлении, образуя между собой «окно».

Проблема перекрывающихся вычислений (Фиксированное окно)

Представьте задачу: дан массив положительных чисел, нужно найти максимальную сумму непрерывного подмассива длиной ровно $K$ .

Пусть массив равен [2, 1, 5, 1, 3, 2], а $K = 3$ . Наивный подход заставит нас проверять каждый блок по очереди:

2 + 1 + 5 = 8
1 + 5 + 1 = 7
5 + 1 + 3 = 9

Заметили проблему? При переходе от первого шага ко второму мы заново складываем числа 1 и 5. Чем больше $K$ , тем больше бесполезной работы мы делаем. В худшем случае сложность такого подхода составит $O(N \cdot K)$ .

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

Sum_{new} = Sum_{old} - Element_{out} + Element_{in}

Теперь сдвиг окна на одну позицию вправо требует ровно двух математических операций независимо от размера $K$ . Мы один раз считаем сумму первых $K$ элементов, а затем просто «скользим» окном до конца массива. Сложность падает до $O(N)$ .

Динамическое окно: когда размер неизвестен

Фиксированное окно — это лишь разминка. Настоящая сила паттерна раскрывается в задачах, где размер окна заранее не задан.

Классический пример — задача Longest Substring Without Repeating Characters. Нужно найти длину самой длинной подстроки, в которой нет повторяющихся символов. Например, в строке "abcabcbb" ответом будет "abc" (длина 3).

Здесь мы не можем просто двигать рамку фиксированного размера. Окно должно вести себя как гусеница:

Расширяться (двигать правый указатель right), пока условие выполняется (все символы внутри уникальны).
Сжиматься (двигать левый указатель left), когда условие нарушается (попался дубликат), пока окно снова не станет валидным.

Чтобы эта механика работала, алгоритму нужна «память» — структура данных, которая отслеживает текущее состояние окна. Для уникальных символов отлично подойдет набор (Set) или массив частот.

На каждом шаге правый указатель добавляет символ в состояние окна. Если символ уже есть в наборе, мы запускаем внутренний цикл: левый указатель удаляет символы из состояния и ползет вправо до тех пор, пока дубликат не выпадет из окна.

Парадокс вложенного цикла: почему это O(N)?

Если вы реализуете переменное скользящее окно, ваш код будет выглядеть примерно так: внешний цикл двигает right от начала до конца, а внутри него находится цикл while, который двигает left.

На первый взгляд, цикл внутри цикла — это верный признак $O(N^2)$ . Но в оценке сложности важна не визуальная вложенность кода, а реальное количество операций.

Давайте проследим за жизненным циклом одного элемента массива:

Правый указатель right может добавить элемент в окно ровно один раз.
Левый указатель left может удалить элемент из окна ровно один раз.

Указатель left никогда не возвращается назад (не сбрасывается в ноль при каждой итерации внешнего цикла). Он только догоняет right. Значит, для массива из $N$ элементов оба указателя суммарно сделают не более $2N$ шагов. Константы отбрасываются, и мы получаем честное $O(N)$ . Этот метод оценки называется амортизационным анализом.

Как распознать паттерн на интервью

Sliding Window — один из самых легко узнаваемых паттернов. Маркеры в условии задачи всегда кричат о нём:

Требуется найти максимальную/минимальную/самую длинную/самую короткую структуру.
Эта структура должна быть непрерывной (подмассив, подстрока, последовательность).
Задано условие валидности (сумма равна $S$ , нет дубликатов, ровно $K$ уникальных элементов).

Если вы видите эти признаки, ваша первая мысль должна быть не о вложенных циклах, а о двух указателях, ползущих слева направо.

Практикум: Переход от O(N^2) к O(N) за один присест

«Решение работает, но можем ли мы сделать его быстрее?» — это самая частая фраза, которую вы услышите на техническом интервью в BigTech сразу после того, как напишете рабочий код. Если ваш первый подход работает за $O(N^2)$ , от вас почти всегда ждут оптимизации до $O(N)$ или $O(N \log N)$ .

В предыдущих главах мы разобрали механику встречных указателей и скользящего окна. Сегодня мы проведем практикум: возьмем две классические задачи, где руки сами тянутся написать вложенные циклы, и шаг за шагом трансформируем их в линейные алгоритмы. Наша цель — натренировать интуицию, которая позволит вам видеть $O(N)$ -решение еще до написания первой строчки кода.

Анатомия O(N²): Почему алгоритм тормозит?

Вложенные циклы возникают там, где мы пытаемся проверить все возможные комбинации.

Типичный наивный алгоритм работает так: внешний цикл фиксирует стартовую точку, а внутренний цикл пробегает оставшуюся часть массива. Главная проблема такого подхода — амнезия. Когда внутренний цикл завершается и внешний делает шаг вперед, внутренний цикл начинается с нуля. Алгоритм «забывает» всю информацию, которую собрал на предыдущей итерации.

Переход от $O(N^2)$ к $O(N)$ всегда строится на одном принципе: перестать сбрасывать второй указатель. Мы должны использовать состояние, достигнутое на предыдущем шаге, чтобы продолжить движение, а не начинать поиск заново.

Кейс 1: Непрерывные подмассивы (Sliding Window)

Рассмотрим задачу Minimum Size Subarray Sum (LeetCode 209). Дан массив положительных чисел и целевое значение $S$ . Нужно найти минимальную длину непрерывного подмассива, сумма элементов которого $\geq S$ .

Пример: массив [2, 3, 1, 2, 4, 3], цель $S = 7$ .

Наивный подход ( $O(N^2)$ ): Мы берем первый элемент (2) и прибавляем к нему следующие, пока не получим $7$ . Нашли подмассив [2, 3, 1, 2], длина 4. Затем мы сдвигаем старт на второй элемент (3) и... снова начинаем суммировать: 3 + 1 + 2 + 4 = 10. Нашли длину 4. И так далее для каждого стартового элемента.

Оптимизация ( $O(N)$ ): Заметим закономерность. Когда мы нашли первый валидный подмассив [2, 3, 1, 2] (сумма 8), правый указатель остановился на индексе 3. Когда мы сдвигаем левый указатель (убираем 2, сумма становится 6), нам не нужно возвращать правый указатель назад. Мы уже знаем, что элементы между левым и правым указателями в сумме дают меньше 7. Правый указатель может только продолжать движение вперед.

Мы превратили два независимых цикла в окно, границы которого двигаются только вправо. Левый указатель догоняет правый, вычитая элементы из суммы, а правый расширяет окно, добавляя новые. Каждый элемент добавляется в сумму ровно один раз и вычитается ровно один раз. Амортизационная сложность — $O(N)$ .

Кейс 2: Фильтрация на месте (Read/Write Pointers)

Теперь возьмем задачу Move Zeroes (LeetCode 283). Дан массив. Нужно переместить все нули в конец, сохранив относительный порядок остальных элементов. Требование: сделать это In-place (без выделения нового массива).

Пример: [0, 1, 0, 3, 12]. Ожидаемый результат: [1, 3, 12, 0, 0].

Наивный подход ( $O(N^2)$ ): Идем по массиву. Видим ноль. Чтобы сдвинуть его в конец, нам нужно сместить все оставшиеся элементы на одну позицию влево, а ноль поставить в конец. Сдвиг массива — это $O(N)$ операция. Если в массиве $N$ нулей, мы сделаем сдвиг $N$ раз. Итоговое время — $O(N^2)$ .

Оптимизация ( $O(N)$ ): Здесь нам поможет подвид паттерна Two Pointers, который называется Указатели чтения и записи (Read/Write Pointers). Оба указателя начинают с начала массива и двигаются в одном направлении, но с разной логикой:

Указатель read работает как разведчик. Он проверяет каждый элемент массива.
Указатель write указывает на позицию, куда нужно записать следующий ненулевой элемент.

Логика невероятно проста: если read видит ненулевой элемент, мы копируем его на позицию write, после чего оба указателя делают шаг. Если read видит ноль, он просто идет дальше, а write остается на месте, ожидая следующего ненулевого числа.

Пройдем по примеру [0, 1, 0, 3, 12]:

Шаг 1: read видит 0. Идет дальше. write остается на индексе 0.
Шаг 2: read видит 1. Копируем 1 на позицию write (индекс 0). Теперь массив [1, 1, 0, 3, 12]. Оба указателя делают шаг.
Шаг 3: read видит 0. Идет дальше. write ждет на индексе 1.
Шаг 4: read видит 3. Копируем 3 на позицию write (индекс 1). Массив [1, 3, 0, 3, 12].
Шаг 5: read видит 12. Копируем на позицию write (индекс 2). Массив [1, 3, 12, 3, 12].

Цикл read завершен за $O(N)$ . Осталось только заполнить нулями все позиции начиная с текущего write и до конца массива. Результат: [1, 3, 12, 0, 0]. Мы решили задачу за один проход, не сдвигая блоки элементов.

Как выбрать правильный паттерн?

На собеседовании вам не скажут: «Примените скользящее окно». Вы должны вывести это из условия. Хотя и Sliding Window, и Two Pointers используют два индекса, их области применения строго разделены.

Маркеры для Sliding Window: Ищите слова «непрерывный» (contiguous), «подмассив» (subarray), «подстрока» (substring). Если вам нужно найти максимальную/минимальную длину или сумму элементов, идущих строго подряд — это скользящее окно.

Маркеры для Two Pointers: Ищите слова «пары» (pairs), «отсортированный массив» (sorted array), «на месте» (in-place), «удаление дубликатов» (remove duplicates). Если порядок элементов не важен, или вам нужно сравнивать элементы с разных концов, или фильтровать массив без дополнительной памяти — используйте два указателя.

Переход от $O(N^2)$ к $O(N)$ — это не магия, а умение управлять состоянием. Всякий раз, когда вы пишете вложенный цикл, задавайте себе вопрос: «Какую работу, проделанную внутренним циклом, я сейчас выбрасываю, чтобы начать заново?». Ответ на этот вопрос укажет вам путь к линейному решению.

Хеш-таблицы: Поиск за O(1) и компромиссы по памяти

В прошлых главах мы научились виртуозно сжимать пространство поиска с помощью паттернов Two Pointers и Sliding Window. Мы избавлялись от вложенных циклов, снижая время с $O(N^2)$ до $O(N)$ . Но у этих подходов есть жесткое требование: данные должны обладать определенной структурой (например, массив должен быть отсортирован, или искомый подмассив должен быть непрерывным).

А что, если массив не отсортирован, сортировать его нельзя (потеряются исходные индексы), а нам нужно мгновенно проверять, встречали ли мы определенный элемент ранее?

Здесь на сцену выходит главный принцип алгоритмической оптимизации: Space-Time Trade-off (компромисс между памятью и временем). Мы можем купить скорость выполнения, заплатив за нее оперативной памятью. Главная «валюта» в этой сделке — хеш-таблицы.

Как купить время за память

Представьте классическую задачу: найти в неотсортированном массиве два числа, дающие в сумме target (оригинальная задача Two Sum).

Без сортировки паттерн встречных указателей не работает. Наивный подход — проверить каждую пару вложенным циклом. Это $O(N^2)$ по времени и $O(1)$ по памяти (In-place).

Но что, если по мере прохода по массиву мы будем «запоминать» каждое увиденное число и его индекс? Находясь на числе $X$ , нам нужно лишь спросить: «А видели ли мы раньше число $Y$ , где $Y = target - X$ ?»

Если структура данных позволяет ответить на этот вопрос за $O(1)$ , общий алгоритм схлопнется до одного прохода — $O(N)$ . Именно такую магию предоставляет хеш-таблица (Hash Map). Мы выделяем дополнительную память $O(N)$ для хранения элементов, но взамен получаем константное время поиска.

Внутреннее устройство: откуда берется O(1)?

Хеш-таблица — это не магия, а хитрое использование обычного массива. Доступ к элементу массива по индексу всегда занимает $O(1)$ . Задача хеш-таблицы — превратить любые данные (строку, объект, большое число) в индекс массива.

Процесс состоит из трех шагов:

Ключ передается в хеш-функцию.
Хеш-функция математически преобразует ключ в целое число (хеш-код).
Это число с помощью операции остатка от деления (%) превращается в индекс массива (корзины).

Проблема коллизий

Массив под капотом хеш-таблицы имеет ограниченный размер. Рано или поздно хеш-функция выдаст одинаковый индекс для двух абсолютно разных ключей. Это называется коллизией.

Самый частый способ разрешения коллизий — метод цепочек (Chaining). Если два ключа попадают в одну корзину, они не перезаписывают друг друга, а выстраиваются в связный список. При поиске алгоритм сначала прыгает в нужную корзину за $O(1)$ , а затем линейно проходит по списку внутри нее.

На собеседованиях в BigTech важно произносить эту оговорку: поиск в хеш-таблице занимает $O(1)$ в среднем случае (Average Case), но $O(N)$ в худшем случае (Worst Case), если все элементы из-за плохой хеш-функции попадут в одну корзину. Современные языки программирования (Java, Python, C++) имеют встроенные механизмы защиты от этого, но алгоритмически худший случай всегда $O(N)$ .

Hash Set против Hash Map

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

Структура	Что хранит	Главный вопрос, на который отвечает	Пример задачи
Hash Set (Множество)	Только уникальные ключи	«Встречали ли мы этот элемент раньше?»	Содержит ли массив дубликаты? (Contains Duplicate)
Hash Map (Словарь)	Пары `Ключ : Значение`	«Какие данные связаны с этим элементом?»	Сколько раз символ встречается в строке? (Valid Anagram)

Если вам не нужно хранить индекс элемента, частоту его появления или любые другие метаданные — всегда используйте Hash Set. Он легче и семантически точнее выражает ваши намерения в коде.

Кульминация: Hash Set внутри Sliding Window

В главе про скользящее окно мы отложили один вопрос: как эффективно проверять валидность состояния внутри динамического окна? Теперь у нас есть инструмент.

Рассмотрим задачу Longest Substring Without Repeating Characters (LeetCode 3). Дана строка, нужно найти длину максимальной подстроки, в которой нет повторяющихся символов.

Логика решения: Мы используем паттерн Sliding Window (два указателя left и right, движущиеся в одном направлении). Чтобы за $O(1)$ понимать, есть ли символ right уже внутри нашего окна, мы будем хранить все символы текущего окна в Hash Set.

Указатель right расширяет окно вправо.
Если символа под right нет в Hash Set, мы добавляем его туда и обновляем максимальную длину.
Если символ уже есть в Hash Set — окно стало невалидным (появился дубликат). Мы начинаем двигать указатель left вправо, удаляя символы из Hash Set, пока дубликат не исчезнет.

Благодаря Hash Set проверка дубликата занимает $O(1)$ . Оба указателя (left и right) проходят по строке только вперед. Амортизационная сложность алгоритма — $O(N)$ по времени. Пространственная сложность — $O(K)$ , где $K$ — размер алфавита (максимальное количество элементов в Hash Set).

Резюме

Хеш-таблицы — это ваш дефолтный инструмент для снижения временной сложности в задачах, где порядок элементов не имеет значения. Увидели необходимость искать элементы «на лету» или подсчитывать частоту — сразу думайте о Hash Map.

Однако на технических интервью за этим часто следует вопрос-ловушка. Вы успешно решили задачу за $O(N)$ времени и $O(N)$ памяти, используя хеш-таблицу. Интервьюер кивает и говорит: «Отлично. А теперь решите эту же задачу, используя $O(1)$ дополнительной памяти».

Хеш-таблица здесь бессильна. Как искать циклы и дубликаты, не выделяя память под историю обхода? Об этом мы поговорим в следующей главе, разбирая паттерн Fast and Slow Pointers.

Паттерн Fast and Slow Pointers: Поиск циклов без лишней памяти

В прошлой главе мы разобрали принцип Space-Time Trade-off: чтобы ускорить поиск до $O(1)$ , мы жертвуем памятью, сохраняя просмотренные элементы в Hash Set. Это отлично работает для поиска дубликатов или проверки уникальности. Но что, если интервьюер усложняет задачу и ставит жесткое ограничение: «Решите задачу за $O(N)$ по времени, но с использованием строго $O(1)$ дополнительной памяти»?

Хеш-таблица здесь уже не поможет — она требует $O(N)$ памяти. Именно для таких ситуаций, когда нужно отследить зацикливание или найти специфическую позицию в последовательности без выделения новой памяти, применяется паттерн Fast and Slow Pointers (Быстрый и медленный указатели).

Проблема зацикливания

Представьте односвязный список — структуру данных, где каждый элемент содержит значение и ссылку на следующий узел. Вы идете по списку, переходя от узла к узлу. Если список конечен, вы в итоге упретесь в конец (нулевую ссылку). Но если в списке есть цикл, когда последний узел указывает на один из предыдущих, вы будете ходить по кругу вечно.

Классическая задача LeetCode 141: Linked List Cycle. Как программно определить, есть ли в списке цикл?

Наивный подход с Hash Set: идем по списку и складываем ссылки на каждый посещенный узел в множество. Если мы пытаемся добавить узел, который уже есть в Hash Set — значит, мы нашли цикл. Сложность по времени: $O(N)$ . Сложность по памяти: $O(N)$ .

Чтобы избавиться от затрат памяти, мы используем алгоритм нахождения цикла Флойда, также известный как «Заяц и Черепаха».

Алгоритм Флойда: Заяц и Черепаха

Идея паттерна гениально проста. Мы запускаем по списку одновременно два указателя, но с разной скоростью:

Медленный указатель (Slow) делает один шаг за итерацию.
Быстрый указатель (Fast) делает два шага за итерацию.

Если цикла нет, быстрый указатель просто достигнет конца списка, и мы вернем ответ «цикла нет». Но если цикл существует, оба указателя рано или поздно окажутся внутри него. И вот здесь начинается самое интересное: быстрый указатель, двигаясь по кругу, неизбежно догонит медленный сзади.

Почему они гарантированно встретятся?

Частый вопрос на собеседованиях: «А может ли быстрый указатель перепрыгнуть через медленный, так и не совпав с ним в одном узле?».

Чтобы ответить на него, нужно посмотреть на систему через призму относительной скорости. Каждый раз, когда медленный указатель делает 1 шаг, а быстрый — 2 шага, расстояние между ними сокращается ровно на 1 узел.

Расстояние не может сократиться на 2 или на 3 узла за раз. Оно уменьшается строго на 1. Следовательно, если быстрый указатель находится позади медленного на расстоянии $K$ узлов, то ровно через $K$ итераций расстояние станет равно нулю. Указатели окажутся в одном узле. Перепрыгнуть друг друга при разнице скоростей в 1 шаг математически невозможно.

Поиск начала цикла (Фаза 2)

Определить наличие цикла (LeetCode 141) — это лишь половина дела. Часто требуется найти конкретный узел, где именно начинается этот цикл (LeetCode 142: Linked List Cycle II).

Точка, где встретились быстрый и медленный указатели, доказывает наличие цикла, но она не обязательно является его началом. Однако эта точка встречи обладает уникальным математическим свойством.

Не погружаясь в сложные алгебраические выводы, зафиксируем главное правило алгоритма Флойда для поиска начала цикла:

Дождитесь встречи Fast и Slow внутри цикла.
Оставьте указатель Fast в точке встречи.
Переместите указатель Slow в самое начало списка.
Теперь двигайте оба указателя с одинаковой скоростью — по одному шагу за итерацию.
Узел, в котором они встретятся во второй раз, и есть точка начала цикла.

Это работает всегда, независимо от длины прямого участка до цикла и длины самого цикла.

Массив как связный список: Выход за рамки

Если бы паттерн Fast and Slow Pointers применялся только к связным спискам, он был бы узкоспециализированным трюком. Настоящая магия BigTech-интервью начинается, когда вы применяете этот паттерн к обычным массивам.

Рассмотрим задачу LeetCode 287: Find the Duplicate Number. Вам дан массив из $N + 1$ целых чисел. Все числа лежат в диапазоне от $1$ до $N$ . Известно, что в массиве есть ровно одно повторяющееся число (оно может повторяться два или более раз). Ограничения: вы не можете изменять массив (In-place сортировка запрещена) и должны использовать строго $O(1)$ дополнительной памяти.

Сортировка запрещена. Hash Set запрещен ограничением памяти. Математические трюки с суммой не работают, так как дубликат может повторяться не два, а три или четыре раза. Как быть?

Ключ к решению — посмотреть на массив как на связный список, где значение элемента является индексом следующего элемента.

Поскольку все значения лежат в диапазоне от $1$ до $N$ , а индексов в массиве $N + 1$ (от $0$ до $N$ ), любое значение в массиве гарантированно указывает на существующий индекс.

Если в массиве есть дубликат (например, два раза встречается число 3), это значит, что из двух разных индексов мы совершим переход в один и тот же индекс 3. В терминах графов и списков — в узел 3 входят две стрелки. Это формирует цикл!

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

Запускаем Slow и Fast указатели из индекса 0.
Переход для Slow: Slow = nums[Slow].
Переход для Fast: Fast = nums[nums[Fast]].
Находим точку их встречи (Фаза 1).
Сбрасываем Slow в 0, замедляем Fast до одного шага и ищем точку начала цикла (Фаза 2).
Точка начала цикла — это и есть искомый дубликат!

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

Резюме

Паттерн Fast and Slow Pointers — это мощный инструмент для работы с последовательностями, где возможны зацикливания. Он позволяет:

Находить циклы за $O(N)$ времени и $O(1)$ памяти.
Находить точку входа в цикл.
Решать нетривиальные задачи на массивах, если элементы можно интерпретировать как указатели на индексы.

В следующей главе мы перейдем к задачам, где данные представлены в виде диапазонов и отрезков, и разберем паттерн Merge Intervals.

Паттерн Merge Intervals: Работа с интервалами и перекрытиями

Представьте, что вы разрабатываете бэкенд для Google Calendar. Пользователь добавляет новую встречу, и система должна мгновенно определить: свободен ли этот слот, или новая встреча накладывается на уже существующие? А если накладывается — как объединить их в один большой блок занятого времени?

В прошлой главе мы искали циклы, манипулируя указателями на конкретные элементы. Теперь мы переходим от точечных значений к диапазонам. Задачи на расписания, бронирование ресурсов, анализ логов активности и объединение IP-подсетей — всё это сводится к алгоритмическому паттерну Merge Intervals (Слияние интервалов).

Анатомия перекрытия

Интервал — это пара чисел $[start, end]$ , где $start \leq end$ .

Главный вопрос любой задачи этого класса: как алгоритмически определить, что два интервала пересекаются?

Допустим, у нас есть интервал $A$ и интервал $B$ . Если мы берем их в случайном порядке, нам придется проверять множество сложных условий: не начинается ли $B$ внутри $A$ , не заканчивается ли он там, не поглощает ли $B$ интервал $A$ целиком.

Но паттерн Merge Intervals опирается на один фундаментальный шаг, который радикально упрощает логику: предварительная сортировка.

Если мы отсортируем все интервалы по времени начала ( $start$ ), мы гарантируем, что $start_A \leq start_B$ . При таком условии интервал $B$ может пересечься с $A$ только в одном случае: если начало $B$ происходит раньше (или одновременно), чем заканчивается $A$ .

Математически это выражается элементарным неравенством: $start_B \leq end_A$ .

Как только мы отсортировали данные, у нас остается всего три сценария взаимного расположения $A$ и $B$ :

Не пересекаются: $start_B > end_A$ . Интервал $B$ начинается строго после завершения $A$ .
Частичное перекрытие: $start_B \leq end_A$ , но $end_B > end_A$ . Интервалы сцепляются.
Полное поглощение: $start_B \leq end_A$ и $end_B \leq end_A$ . Интервал $B$ целиком находится внутри $A$ .

Базовый алгоритм слияния (LeetCode 56)

Классическая задача звучит так: дан массив интервалов, объедините все перекрывающиеся интервалы и верните массив неперекрывающихся.

Без сортировки нам пришлось бы сравнивать каждый интервал с каждым — это $O(N^2)$ . Сортировка занимает $O(N \log N)$ , но после нее мы можем решить задачу за один проход ( $O(N)$ ).

Логика линейного прохода:

Сортируем исходный массив по $start$ .
Создаем пустой список merged для хранения результата.
Помещаем первый интервал из отсортированного массива в merged.
Идем по оставшимся интервалам. На каждом шаге сравниваем текущий интервал с последним интервалом в списке merged.

Если текущий интервал пересекается с последним в merged (то есть $start_{current} \leq end_{merged}$ ), мы их сливаем.

Слияние происходит не путем создания нового объекта, а через обновление границы уже лежащего в merged интервала. Новой границей окончания становится $\max(end_{merged}, end_{current})$ .

Если же пересечения нет, мы просто добавляем текущий интервал в конец списка merged, и теперь он становится «последним», с которым будут сравниваться следующие.

Оптимизация: Вставка без полной сортировки (LeetCode 57)

Часто на собеседованиях задачу усложняют. Что, если массив интервалов уже отсортирован и не имеет перекрытий, а вам нужно вставить в него всего один новый интервал (Insert Interval)?

Наивный подход: добавить новый интервал в конец, запустить сортировку всего массива и применить стандартный алгоритм. Сложность будет $O(N \log N)$ .

Но поскольку массив уже отсортирован, мы можем решить задачу за строгое $O(N)$ без вызова функции сортировки. Мы делим процесс на три фазы:

До перекрытия: Проходим по массиву и добавляем в результат все интервалы, которые заканчиваются строго до начала нового интервала ( $end_{current} < start_{new}$ ).
Слияние: Как только находим пересечение, мы не добавляем интервалы в результат сразу. Мы расширяем границы нашего new интервала, сливая его со всеми пересекающимися: $start_{new} = \min(start_{new}, start_{current})$ $end_{new} = \max(end_{new}, end_{current})$ Это продолжается, пока текущие интервалы пересекаются с обновляемым new. После выхода из этого цикла добавляем итоговый new в результат.
После перекрытия: Добавляем все оставшиеся интервалы (они гарантированно не пересекаются, так как начинаются позже $end_{new}$ ).

Анализ сложности

Временная сложность базового паттерна Merge Intervals всегда упирается в сортировку. Сам проход по массиву занимает $O(N)$ , но сортировка требует $O(N \log N)$ . По правилам Big-O мы оставляем доминирующий член, поэтому итоговая временная сложность — $O(N \log N)$ .

Пространственная сложность (Space Complexity) зависит от двух факторов:

Память, требуемая алгоритмом сортировки под капотом языка (например, Timsort в Python или IntroSort в C++ требуют от $O(\log N)$ до $O(N)$ дополнительной памяти).
Память для хранения результата. В худшем случае, если ни один интервал не пересекается, массив merged будет содержать $N$ элементов, что дает $O(N)$ .

Паттерн Merge Intervals элегантно решает задачи, где нас интересует итоговое состояние расписания — какие блоки времени заняты. Но что, если нас спросят: «Какое максимальное количество переговорных комнат потребуется одновременно?» Здесь простого слияния уже недостаточно, так как нам нужно отслеживать динамику наложения в моменте. Для решения таких задач нам потребуется структура данных, способная эффективно выдавать минимальный элемент — Min-Heap, к которой мы перейдем в следующих главах.

Стек и Дек: Монотонный стек для поиска ближайших элементов

Представьте задачу: перед вами массив прогноза температур на ближайшие дни. Для каждого дня нужно ответить на вопрос: через сколько дней станет теплее?

Если температура сегодня 73 градуса, а завтра 74 — ответ «через 1 день». Но если после 75 градусов идут 71, 69 и 72, то для 75 придется просматривать массив далеко вперед. Наивный подход с вложенным циклом очевиден: берем день и бежим вперед, пока не найдем число больше. В худшем случае (когда температуры убывают) это дает сложность $O(N^2)$ . При ограничении в $10^5$ элементов, о котором мы говорили ранее, такое решение не пройдет Time Limit.

Нам нужен алгоритм за $O(N)$ . И ключ к нему — изменение парадигмы. Вместо того чтобы для каждого элемента активно искать ответ в будущем, мы заставим элементы «ждать» в специальной структуре данных, пока ответ сам не придет к ним.

Концепция Монотонного стека

Обычный стек (Stack) работает по принципу LIFO (Last In, First Out). Мы можем класть элементы на вершину и снимать с вершины.

Монотонный стек — это не новая структура данных, а паттерн использования обычного стека. Правило простое: элементы в стеке всегда должны быть отсортированы (монотонно возрастать или убывать).

Для задачи «найти ближайший больший элемент» (Next Greater Element) мы используем монотонно убывающий стек. В нем хранятся элементы, которые еще не нашли свой ответ. Они лежат там и ждут, когда в массиве появится кто-то больше их.

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

Механика на примере Daily Temperatures

Возьмем массив температур: [75, 71, 69, 72, 76]. В стек мы будем класть не сами значения, а их индексы, чтобы легко вычислять расстояние в днях.

75 (индекс 0): Стек пуст. Просто кладем индекс 0 в стек. Стек: [0].
71 (индекс 1): 71 меньше 75. Порядок не нарушается (стек убывающий). Кладем в стек. Стек: [0, 1].
69 (индекс 2): 69 меньше 71. Кладем в стек. Стек: [0, 1, 2]. Сейчас в стеке ждут своего часа температуры 75, 71 и 69.
72 (индекс 3): Внимание! 72 больше, чем температура на вершине стека (индекс 2, значение 69).
- Значит, для 69 первый более теплый день — это сегодня (72).
- Извлекаем 2 из стека. Разница индексов: $3 - 2 = 1$ день. Записываем ответ.
- Снова смотрим на вершину: там индекс 1 (значение 71). 72 тоже больше 71!
- Извлекаем 1. Разница индексов: $3 - 1 = 2$ дня. Записываем ответ.
- Следующая вершина — индекс 0 (значение 75). 72 меньше 75. Остановка.
- Кладем индекс 3 в стек. Стек: [0, 3].

Шаблон кода

Этот паттерн имеет строгий и элегантный шаблон, который переносится из задачи в задачу почти без изменений:

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = [] # хранит индексы

    for i in range(n):
        # Пока стек не пуст и текущая температура больше температуры на вершине
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index # вычисляем расстояние

        stack.append(i) # текущий элемент встает в очередь ожидания

    return answer

Сложность этого кода — $O(N)$ . Несмотря на цикл while внутри for, мы применяем амортизационный анализ: каждый индекс добавляется в стек ровно один раз и извлекается из стека максимум один раз. Внутренний цикл суммарно за все итерации выполнится не более $N$ раз. Итого $2N$ операций, что дает $O(N)$ .

Дек: Когда стека недостаточно

Стек идеален, когда нам нужно работать только с самым «свежим» отложенным элементом (вершиной). Но что, если задача требует удалять элементы не только с конца, но и с начала?

Здесь на сцену выходит Дек (Deque — Double-Ended Queue). Это двусторонняя очередь, которая позволяет добавлять и удалять элементы с обоих концов за $O(1)$ .

В задачах BigTech дек чаще всего используется для расширения паттерна скользящего окна (Sliding Window). Классический пример — Sliding Window Maximum (LeetCode 239). Вам дано окно размера $K$ , которое скользит по массиву, и нужно находить максимум в окне на каждом шаге.

Если использовать обычное окно, поиск максимума займет $O(K)$ , а общая сложность составит $O(N \times K)$ .

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

Дек хранит индексы кандидатов на максимум.
При добавлении нового элемента мы удаляем с конца дека все элементы, которые меньше нового (они никогда не станут максимумом, так как новый элемент больше и пробудет в окне дольше). Это логика монотонного стека.
Отличие от стека: на каждом шаге мы проверяем начало дека. Если индекс на левом конце дека выпал за границы скользящего окна, мы удаляем его спереди (операция popleft()).
В результате максимум текущего окна всегда находится в начале дека.

Дек объединяет в себе фильтрацию бесполезных элементов (как в монотонном стеке) и контроль времени жизни элементов (как в скользящем окне).

Очереди и Heap: Топ-K элементов и слияние списков

Представьте, что вы разрабатываете рекомендательную систему для YouTube. У вас есть массив из 10 миллионов видео, и вам нужно вывести на главную страницу ровно 10 роликов с наивысшим рейтингом. Очевидное решение — отсортировать весь массив по убыванию рейтинга и взять первые 10 элементов. Сортировка займет $O(N \log N)$ времени. Для 10 миллионов записей это около 230 миллионов операций. Но зачем нам сортировать все 10 миллионов видео, если нас интересуют только 10 из них?

В прошлой главе мы рассматривали монотонный стек, который помогает искать ближайшие экстремумы в жестко заданном окне. Но когда нам нужно динамически находить глобальный максимум или минимум в потоке данных, на сцену выходит структура данных, способная решить задачу с видео за $O(N \log K)$ — Очередь с приоритетом (Priority Queue), реализованная на базе Кучи (Heap).

Анатомия Кучи (Heap)

Куча — это древовидная структура данных, которая поддерживает одно главное правило: значение родительского узла всегда больше либо равно (в Max-Heap) или меньше либо равно (в Min-Heap) значений его потомков.

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

Физически куча почти всегда хранится не как дерево с указателями, а как обычный плоский массив. Если родитель находится под индексом $i$ , то его левый потомок лежит по индексу $2i + 1$ , а правый — по индексу $2i + 2$ .

Сложность базовых операций:

Узнать минимум/максимум (посмотреть на корень): $O(1)$
Добавить новый элемент: $O(\log N)$
Удалить минимум/максимум (извлечь корень): $O(\log N)$

При добавлении новый элемент ставится в конец массива (на дно дерева), а затем «всплывает» (sift-up), меняясь местами с родителями, пока не восстановится свойство кучи.

Паттерн Top-K: Поиск K наибольших элементов

Вернемся к задаче с 10 миллионами видео. Как найти 10 лучших за один проход по массиву? Здесь применяется классический алгоритмический паттерн Top-K Elements.

Парадоксально, но чтобы найти K наибольших элементов, нам нужна Min-Heap (куча минимумов), размер которой мы жестко ограничим числом K.

Логика работы паттерна:

Мы идем по массиву и добавляем элементы в Min-Heap.
Как только размер кучи превышает K, мы извлекаем (удаляем) корень.
Поскольку это Min-Heap, в корне всегда лежит самый маленький элемент из текущей кучи. Удаляя его, мы избавляемся от «слабейшего» кандидата.
В итоге, после прохода по всему массиву, в куче останутся ровно K элементов — и это будут K самых больших элементов массива.

Сложность этого подхода составляет $O(N \log K)$ . Мы делаем N шагов, и на каждом шаге операция с кучей занимает $O(\log K)$ , так как размер кучи никогда не превышает K. Для 10 миллионов видео и $K = 10$ , $\log_2 10 \approx 3.3$ . Итоговая сложность — около 33 миллионов операций вместо 230 миллионов при полной сортировке.

Паттерн K-way Merge: Слияние нескольких списков

В главе про два указателя мы обсуждали, как слить два отсортированных массива: мы ставим по указателю на начало каждого и на каждом шаге выбираем меньший элемент. Но что делать, если на вход поступает K отсортированных связных списков? (Это знаменитая задача Merge K Sorted Lists).

Сравнивать K указателей на каждом шаге вручную — это $O(K)$ времени на один элемент, что даст общую сложность $O(N \cdot K)$ , где $N$ — общее количество элементов во всех списках.

Куча элегантно масштабирует паттерн двух указателей:

Помещаем головы всех K списков в Min-Heap. В куче элементы сортируются по значению узла. Это занимает $O(K \log K)$ .
Извлекаем корень кучи — это гарантированно самый маленький узел среди всех текущих указателей. Добавляем его в наш итоговый ответ.
Сдвигаем указатель извлеченного списка на следующий узел и добавляем этот новый узел в кучу ( $O(\log K)$ ).
Повторяем, пока куча не опустеет.

Итоговая временная сложность снижается до $O(N \log K)$ . Мы заменили линейный поиск минимума среди K элементов на логарифмический.

Динамические перекрытия: Meeting Rooms II

В главе про интервалы мы научились сливать пересекающиеся отрезки времени. Теперь рассмотрим задачу Meeting Rooms II, которую мы обещали разобрать: дан массив интервалов встреч (время начала и окончания), нужно определить минимальное количество переговорных комнат, чтобы провести все встречи без накладок.

Здесь нам не нужно сливать интервалы в один. Нам нужно знать, сколько комнат занято одновременно в момент начала новой встречи.

Алгоритм с использованием Min-Heap:

Сортируем все встречи по времени начала. Это гарантирует, что мы обрабатываем события в хронологическом порядке.
Создаем Min-Heap, в которой будем хранить время окончания встреч, идущих прямо сейчас. Корень кучи — это время окончания встречи, которая закончится раньше всех.
Берем очередную встречу. Сравниваем ее время начала с корнем кучи.
- Если время начала $\geq$ корня кучи, значит, самая ранняя встреча уже закончилась. Комната освободилась! Мы извлекаем корень (освобождаем комнату) и добавляем в кучу время окончания новой встречи (занимаем эту же комнату).
- Если время начала $<$ корня кучи, значит, ни одна из текущих встреч еще не закончилась. Нам нужна новая комната. Мы просто добавляем время окончания новой встречи в кучу.
В конце размер кучи будет равен максимальному количеству одновременно занятых комнат.

В этой задаче куча выступает в роли умного планировщика. Она избавляет нас от необходимости проверять все занятые комнаты — она всегда держит «на поверхности» ту комнату, которая освободится первой.

Куча — это незаменимый инструмент, когда задача требует постоянного доступа к экстремумам (минимумам или максимумам) в условиях меняющихся данных. Если в условии есть слова «Топ K», «K-й наименьший/наибольший элемент» или требуется динамическое расписание — первым делом примеряйте паттерны Priority Queue.

Оценка памяти: In-place алгоритмы против выделения новых структур

До сих пор мы охотно жертвовали памятью ради скорости. Мы использовали Hash Maps для мгновенного поиска и Priority Queues для отслеживания топов, сводя квадратичное время к линейному или логарифмическому. Это классический Space-Time Trade-off. Но на интервью в BigTech часто звучит фраза: «Отличное решение за $O(N)$ . А теперь перепишите его так, чтобы пространственная сложность стала $O(1)$ ».

Требование $O(1)$ по памяти (In-place) — это не просто проверка на знание хитрых трюков. В высоконагруженных системах память стоит дорого не только в гигабайтах, но и в процессорном времени.

Скрытая цена $O(N)$ памяти

Когда алгоритм создает новую структуру данных, пропорциональную размеру входа, происходят три скрытых процесса, которые замедляют выполнение:

Аллокация (Allocation overhead). Операционная система должна найти непрерывный блок свободной памяти нужного размера. Это системный вызов, который требует времени.
Сборка мусора (Garbage Collection). В языках вроде Java, Python или C# выделенная память рано или поздно должна быть очищена. Частые аллокации временных массивов провоцируют паузы сборщика мусора (GC pauses), вызывая микрофризы приложения.
Промахи кэша (Cache Misses). Процессор работает быстрее всего с данными, которые уже загружены в его L1/L2 кэш. Когда вы читаете из старого массива и пишете в новый, вы заставляете процессор постоянно переключаться между разными участками оперативной памяти.

In-place алгоритмы решают эти проблемы. Они переиспользуют память, выделенную под входные данные, перезаписывая их. Это дает нулевые накладные расходы на аллокацию и идеальную локальность кэша.

Массив как собственная хеш-таблица

Классический сценарий, где стандартные алгоритмы не подходят из-за ограничений по памяти — это задачи на поиск дубликатов или пропущенных чисел.

Представьте задачу (LeetCode 442: Find All Duplicates in an Array): дан массив длины $N$ , в котором все числа лежат в диапазоне от $1$ до $N$ . Некоторые числа встречаются один раз, некоторые — дважды. Нужно найти все дубликаты.

Решение «в лоб» с Hash Set требует $O(N)$ дополнительной памяти. Но ограничение значений (от $1$ до $N$ ) — это мощнейший сигнал от интервьюера. Если значения элементов совпадают с допустимыми индексами массива, мы можем использовать сам входной массив как хеш-таблицу.

Паттерн Sign-Flipping (Инверсия знака)

Идея заключается в том, чтобы использовать знак числа как маркер «мы здесь уже были».

Алгоритм:

Идем по массиву. Берем текущее значение по модулю (так как оно могло быть изменено ранее): $val = |nums[i]|$ .
Вычисляем индекс, на который указывает это значение: $idx = val - 1$ (минус один, так как индексы начинаются с нуля).
Смотрим на число по этому индексу: $nums[idx]$ .
Если оно положительное — мы видим число $val$ впервые. Делаем $nums[idx]$ отрицательным: $nums[idx] = -nums[idx]$ .
Если оно уже отрицательное — значит, мы уже обращались к этому индексу ранее. Следовательно, число $val$ — дубликат!

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

Абсолютное значение ячейки хранит исходные данные массива.
Знак ячейки хранит информацию о том, встречалось ли число, равное индексу ячейки + 1.

Кодирование двух значений в одном (Modulo Arithmetic)

Трюк со знаком работает только если исходные числа строго положительные. Что делать, если в массиве есть нули или отрицательные числа, но нам всё равно нужно хранить два состояния в одной ячейке за $O(1)$ памяти?

На помощь приходит модульная арифметика. Мы можем закодировать старое и новое значение в одном числе, используя константу $M$ , которая строго больше любого возможного значения в массиве.

Формула кодирования: $NewState = OldValue + (TargetValue \pmod M) \times M$

Как это работает на практике? Допустим, у нас есть массив, и мы хотим заменить каждый элемент на другой, но так, чтобы в процессе обхода не потерять исходные значения (например, в задаче LeetCode 38: Count and Say или при поворотах матриц).

Пусть максимальное число в массиве равно $99$ . Мы выбираем $M = 100$ . В ячейке лежит $OldValue = 45$ . Мы хотим записать туда $TargetValue = 82$ .

Применяем формулу: $NewState = 45 + (82 \pmod{100}) \times 100 = 45 + 82 \times 100 = 8245$ .

Теперь в числе $8245$ упакованы оба значения:

Чтобы получить старое значение, берем остаток от деления на $M$ : $8245 \pmod{100} = 45$ .
Чтобы получить новое значение, делим на $M$ нацело: $8245 / 100 = 82$ .

Мы модифицировали массив In-place, сохранив доступ к оригинальным данным для последующих итераций. В конце достаточно пройтись по массиву еще раз и поделить все элементы на $M$ , чтобы оставить только новые значения.

Стратегия на интервью

Когда вы видите задачу, требующую оптимизации памяти, придерживайтесь следующего алгоритма:

Никогда не начинайте с In-place трюков. Сначала озвучьте решение с выделением памяти (Hash Map, новый массив). Это покажет интервьюеру, что вы умеете решать задачу стандартными, надежными методами.
Ищите подсказки в ограничениях (Constraints).
- Если элементы массива ограничены диапазоном $[1, N]$ или $[0, N-1]$ — это прямой сигнал к использованию массива как хеш-таблицы (index mapping).
- Если массив отсортирован — это сигнал к использованию Two Pointers (Read/Write указатели, которые мы разбирали ранее).
Оценивайте допустимость мутации. В реальном продакшене изменение входных данных (особенно передаваемых по ссылке) часто считается антипаттерном (side effect). Обязательно спросите интервьюера: "Могу ли я модифицировать входной массив?". Если ответ «нет», требование $O(1)$ памяти обычно снимается.

Бинарные деревья: Глубокое погружение в DFS и BFS

В массивах и связных списках путь всегда один — от начала к концу. В деревьях на каждом шаге возникает выбор: куда идти дальше? Именно эта нелинейность делает деревья идеальным инструментом для проверки того, как вы управляете состоянием и понимаете рекурсию. Большинство задач на графы, парсинг выражений и иерархии в BigTech сводятся к одному фундаментальному навыку: умению правильно обойти бинарное дерево.

Анатомия бинарного дерева

Бинарное дерево — это структура данных, состоящая из узлов. Каждый узел содержит значение и максимум две ссылки: на левого и правого потомка.

Ключевые термины, которыми оперируют в задачах:

Корень (Root) — самый верхний узел, точка входа в дерево.
Лист (Leaf) — узел, у которого нет потомков (обе ссылки указывают на null).
Высота (Height) — максимальное количество ребер от корня до самого глубокого листа.

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

Обход в глубину: Depth-First Search (DFS)

Философия DFS проста: идти вперед, пока не упрешься в тупик (лист), затем вернуться на шаг назад и попробовать другой путь.

Технически DFS реализуется через стек. Чаще всего — через стек вызовов (Call Stack) с помощью рекурсии. Это делает код невероятно лаконичным, но скрывает под капотом выделение памяти. Пространственная сложность рекурсивного DFS составляет $O(H)$ , где $H$ — высота дерева.

В зависимости от того, в какой момент мы обрабатываем текущий узел по отношению к его потомкам, DFS делится на три классических порядка:

Pre-order (Прямой обход): Узел $\rightarrow$ Левое поддерево $\rightarrow$ Правое поддерево. Применение: Копирование дерева, сериализация (сохранение структуры в строку).
In-order (Симметричный обход): Левое поддерево $\rightarrow$ Узел $\rightarrow$ Правое поддерево. Применение: В бинарных деревьях поиска (BST) этот обход выдает элементы строго по возрастанию.
Post-order (Обратный обход): Левое поддерево $\rightarrow$ Правое поддерево $\rightarrow$ Узел. Применение: Удаление дерева, вычисление высоты или размера поддеревьев (когда ответ для узла зависит от ответов его детей).

Ключевой инсайт DFS: Рекурсивный DFS посещает каждый узел дерева ровно три раза: при спуске в него, при возврате из левого поддерева и при возврате из правого. Разница между Pre, In и Post-order заключается лишь в том, на каком из этих трех визитов вы пишете логику задачи.

Обход в ширину: Breadth-First Search (BFS)

Философия BFS — это круги на воде. Мы сначала исследуем всех соседей на текущем уровне, и только потом переходим на следующий.

Если DFS использует стек (LIFO), то BFS опирается на очередь (Queue, FIFO). Мы добавляем корень в очередь, а затем в цикле извлекаем узел, обрабатываем его и добавляем в конец очереди его потомков.

Пространственная сложность BFS оценивается иначе. В очереди одновременно находятся узлы одного уровня. В худшем случае (полное бинарное дерево) на самом нижнем уровне располагается $N/2$ узлов. Следовательно, пространственная сложность BFS составляет $O(W)$ , где $W$ — максимальная ширина дерева.

Поскольку BFS гарантирует, что мы посещаем узлы в порядке увеличения их расстояния от корня, этот алгоритм является золотым стандартом для задач на поиск кратчайшего пути в невзвешенных графах и деревьях.

DFS против BFS: Как выбрать?

На собеседовании выбор между DFS и BFS — это первое архитектурное решение, которое вы должны озвучить. Оба алгоритма посещают все узлы за время $O(N)$ , поэтому выбор зависит от того, что именно вы ищете и какова форма дерева.

Критерий	DFS (Depth-First Search)	BFS (Breadth-First Search)
Структура под капотом	Стек (Call Stack)	Очередь (Queue)
Память	$O(H)$ , где $H$ — высота	$O(W)$ , где $W$ — ширина
Идеально подходит для	Проверки путей от корня до листа, задач «собери данные снизу вверх»	Поиска кратчайшего пути, поуровневого анализа
Худший сценарий памяти	Вырожденное дерево (Linked List): $O(N)$ памяти	Полное сбалансированное дерево: $O(N/2) = O(N)$ памяти

Понимание механики этих двух обходов — это фундамент. Следующий шаг — научиться применять их как готовые шаблоны для извлечения конкретных данных, будь то сбор узлов по уровням или передача состояния от корня к листьям.

Паттерн Tree Breadth-First Search: Поуровневый обход

Представьте, что вам нужно посмотреть на бинарное дерево строго с правой стороны и выписать только те узлы, которые вы видите. Базовый алгоритм BFS, который мы разобрали ранее, помещает узлы в очередь: [1, 2, 3, 4, 5, 6, 7]. Но глядя на этот плоский массив, как понять, где заканчивается второй уровень и начинается третий? Стандартный BFS смешивает поколения узлов в одну сплошную линию.

Чтобы решать задачи, где важна структура уровней (найти среднее значение на каждом ярусе, соединить соседей, вывести зигзагом), нам нужен Паттерн Tree BFS. Это надстройка над классическим поиском в ширину, которая изолирует каждый уровень дерева на лету.

Механика паттерна: «Заморозка» размера очереди

Секрет поуровневого обхода заключается всего в одной дополнительной переменной — размере очереди на момент начала итерации.

Когда мы входим в цикл обработки очередного уровня, в очереди находятся только узлы этого уровня. Если мы зафиксируем их количество в переменную level_size, мы сможем запустить внутренний цикл for, который отработает ровно level_size раз.

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue) # ЗАМОРОЗКА: сколько узлов на текущем уровне
        current_level = []

        # Обрабатываем строго зафиксированное количество узлов
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            # Добавляем детей следующего уровня
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(current_level)

    return result

Внутренний цикл извлекает узлы текущего уровня и одновременно добавляет в конец очереди их детей. Поскольку цикл ограничен заранее вычисленным level_size, он остановится ровно в тот момент, когда закончатся узлы текущего уровня, и не тронет узлы следующего поколения, которые только что были добавлены.

Практическое применение: Binary Tree Right Side View

Вернемся к задаче из начала статьи: LeetCode 199 (Binary Tree Right Side View). Нам нужно вернуть значения узлов, которые видны, если смотреть на дерево справа.

Имея в арсенале паттерн Tree BFS, задача решается элементарно. Нам не нужно строить сложные проекции. Достаточно понять одно правило: самый правый видимый узел на любом уровне — это просто последний узел, обработанный внутренним циклом for.

def rightSideView(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.popleft()

            # Если это последняя итерация внутреннего цикла,
            # значит это самый правый узел текущего уровня
            if i == level_size - 1:
                result.append(node.val)

            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)

    return result

Мы не сохраняем весь уровень в массив current_level, как в базовом шаблоне, а просто перехватываем значение на последней итерации (i == level_size - 1). Это экономит память и делает код элегантным.

Вариация: Зигзагообразный обход

Иногда задачи требуют не просто прочитать уровни, а изменить порядок их чтения. Классический пример — LeetCode 103 (Binary Tree Zigzag Level Order Traversal). Уровни нужно читать поочередно: слева направо, затем справа налево, затем снова слева направо.

Паттерн Tree BFS остается неизменным. Мы добавляем лишь флаг направления и двустороннюю очередь (deque) для сборки самого уровня:

Создаем булеву переменную left_to_right = True.
Внутри цикла while собираем уровень. Если left_to_right истинно, добавляем значения в конец списка уровня. Если ложно — вставляем в начало (или используем appendleft у дека).
В конце каждой итерации while инвертируем флаг: left_to_right = not left_to_right.

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

Оценка сложности

Временная сложность паттерна всегда составляет $O(N)$ , где $N$ — общее количество узлов в дереве. Несмотря на наличие вложенного цикла for внутри while, каждый узел дерева помещается в очередь ровно один раз и извлекается ровно один раз.

Пространственная сложность определяется максимальным размером очереди. Как мы помним из предыдущей главы, в худшем случае (полное бинарное дерево) на последнем уровне находится $N/2$ узлов. Следовательно, очередь потребует $O(N)$ памяти.

Кроме того, если задача требует вернуть массив массивов (как в базовом Level Order Traversal), сама структура ответа также займет $O(N)$ памяти.

Паттерн Tree BFS — это ультимативный инструмент для любых задач, где в условии фигурируют слова «уровень», «ярус», «глубина», «соседи по горизонтали». Однако, если задача требует передавать информацию от корня к листьям и обратно (например, найти максимальный путь), очередь становится неудобной. Для таких случаев нам понадобится рекурсивный спуск, который мы разберем далее.

Паттерн Tree Depth-First Search: Рекурсивный спуск и возврат значений

Мы уже знаем, что DFS погружается в дерево максимально глубоко, используя стек вызовов. Но на собеседованиях в BigTech вас редко попросят просто «обойти дерево». Задачи строятся вокруг того, как данные перемещаются между узлами во время этого обхода.

Паттерн Tree DFS — это не просто порядок посещения узлов (Pre-order, In-order, Post-order). Это управление двумя встречными потоками информации: тем, что родитель сообщает потомкам, и тем, что потомки возвращают родителю.

Два направления потока данных

Любая рекурсивная функция на дереве может передавать данные двумя путями:

Top-Down (сверху вниз): Родительский узел вычисляет какое-то состояние и передает его своим дочерним узлам через аргументы функции. Дочерний узел получает контекст, о котором сам бы не догадался.
Bottom-Up (снизу вверх): Дочерние узлы делают вычисления и передают результат обратно родителю через возвращаемое значение функции (return). Родитель ждет ответов от детей, чтобы сделать свой финальный вывод.

Умение декомпозировать задачу на эти два потока — ключ к решению 90% задач на деревья.

Top-Down: Передача состояния вниз

В подходе Top-Down мы воспринимаем рекурсию как эстафету. Каждый узел получает палочку (текущее состояние), добавляет к ней свой вклад и передает дальше.

Классический пример — задача Path Sum (LeetCode 112). Нужно проверить, существует ли путь от корня до листа, сумма значений узлов которого равна targetSum.

Когда мы стоим на конкретном узле, сам по себе он не знает, какова сумма элементов над ним. Эту информацию ему должен спустить родитель.

Вместо того чтобы накапливать сумму и сравнивать ее в конце, элегантнее вычитать значение текущего узла из искомой суммы и передавать остаток вниз:

Родитель вызывает ребенка, передавая ему targetSum - node.val.
Если мы дошли до листа (нет обоих детей), проверяем: равен ли остаток значению этого листа? Если да — путь найден.

В этом паттерне основная логика выполняется до рекурсивных вызовов (ближе к Pre-order обходу). Мы формируем состояние и проталкиваем его глубже.

Bottom-Up: Сбор ответов снизу

Подход Bottom-Up работает иначе: узел заявляет «я не могу дать ответ, пока не спрошу своих детей». Это классическая парадигма «разделяй и властвуй».

Пример — Maximum Depth of Binary Tree (LeetCode 104). Нужно найти максимальную глубину дерева.

Может ли корень сразу сказать свою глубину? Нет. Но он знает правило: моя глубина равна 1 плюс максимальная из глубин моих поддеревьев.

Логика работы:

Спрашиваем левого ребенка: «Какая у тебя глубина?». Ждем.
Спрашиваем правого ребенка: «Какая у тебя глубина?». Ждем.
Получив два числа, выбираем максимальное, прибавляем 1 (за себя) и возвращаем это число своему родителю.

Здесь основная работа происходит после возврата из рекурсивных вызовов (строгий Post-order обход). Базовый случай (база рекурсии) — это пустой узел (null), который возвращает глубину 0.

Мастер-уровень: Комбинация потоков и глобальное состояние

Самые интересные задачи FAANG требуют использования Bottom-Up обхода для сбора данных от детей, но при этом искомый ответ не всегда является тем значением, которое функция возвращает наверх.

Разберем задачу Diameter of Binary Tree (LeetCode 543). Диаметр — это длина самого длинного пути между любыми двумя узлами. Этот путь не обязан проходить через корень.

Ловушка: Многие пытаются написать функцию, которая возвращает диаметр. Но чтобы посчитать самый длинный путь, проходящий через текущий узел (в виде перевернутой буквы V), узлу нужно знать высоту левого и правого поддеревьев, а не их диаметры.

Путь через текущий узел равен сумме высот левого и правого поддеревьев: $L + R$ .

Решение: Наша рекурсивная функция будет работать по паттерну Bottom-Up и возвращать высоту поддерева. Но попутно, прямо внутри функции, мы будем вычислять потенциальный диаметр $L + R$ и обновлять внешнюю (глобальную) переменную, если этот диаметр больше найденного ранее.

Алгоритм для каждого узла:

Рекурсивно получаем высоту левого поддерева $L$ .
Рекурсивно получаем высоту правого поддерева $R$ .
Мутация состояния: Сравниваем $L + R$ с глобальной переменной max_diameter и обновляем ее при необходимости.
Возврат значения: Возвращаем родителю свою высоту: $1 + \max(L, R)$ .

Этот шаблон — Post-order обход с обновлением внешнего состояния — решает целый класс сложных задач (например, Binary Tree Maximum Path Sum). Функция выполняет служебную роль (считает высоту/сумму ветви), а реальный ответ накапливается сбоку.

Как выбрать подход на интервью?

Столкнувшись с задачей на бинарное дерево, задайте себе два вопроса:

Могу ли я определить ответ для текущего узла, зная только его значение и параметры, переданные сверху? Если да, и ответ можно передать дальше вниз — используйте Top-Down. (Примеры: проверка пути, поиск узла с заданным свойством).
Нужны ли мне ответы от дочерних узлов, чтобы вычислить ответ для текущего? Если узел зависит от результатов своих детей — используйте Bottom-Up. (Примеры: подсчет узлов, вычисление высоты, проверка сбалансированности).

Если задача просит найти максимум/минимум среди всех возможных путей, которые могут изгибаться внутри дерева (как диаметр) — используйте Bottom-Up для сбора линейных характеристик (высоты), и обновляйте глобальный ответ на каждом узле.

Графы: Представление в памяти и выбор структуры данных

Деревья, которые мы глубоко исследовали ранее, — это лишь частный, строго ограниченный случай графа. У дерева есть корень, строгая иерархия «родитель-потомок» и абсолютный запрет на циклы. Снимите эти ограничения — разрешите любому узлу ссылаться на любой другой, добавьте возможность ходить по кругу, уберите выделенный корень — и вы получите граф.

В графах мы оперируем двумя главными сущностями: вершинами (Vertices, обозначаются как $V$ ) и ребрами (Edges, обозначаются как $E$ ). В отличие от дерева, где количество ребер всегда равно $V - 1$ , в графе количество ребер может варьироваться от $0$ до $V^2$ .

Главная сложность алгоритмических задач на графы заключается не в самом обходе, а в подготовке. В задачах на деревья LeetCode заботливо передает вам ссылку на готовый объект TreeNode root. В графовых задачах вам чаще всего дают просто числа: количество вершин $n$ и сырой двумерный массив связей edges = [[0, 1], [1, 2]].

Компьютер не видит кружочков и линий. Прежде чем запустить алгоритм, вы должны перевести этот сырой массив в структуру данных, по которой удобно перемещаться. От выбора этой структуры зависит, уложится ли ваше решение в ограничения по памяти (Space Complexity) и времени (Time Complexity).

Матрица смежности (Adjacency Matrix)

Самый интуитивный способ представить связи между вершинами — создать двумерный массив (матрицу) размером $V \times V$ .

Если между вершиной $i$ и вершиной $j$ есть ребро, мы записываем в ячейку matrix[i][j] единицу (или вес ребра). Если связи нет — записываем ноль. Для неориентированного графа матрица всегда будет симметричной относительно главной диагонали: если можно пройти из $A$ в $B$ , то matrix[A][B] = 1 и matrix[B][A] = 1.

Преимущества:

Проверка наличия ребра между любыми двумя вершинами занимает эталонное $O(1)$ . Вы просто смотрите в ячейку matrix[i][j].
Легко добавлять и удалять ребра.

Недостатки:

Потребление памяти всегда составляет $O(V^2)$ , независимо от реального количества ребер.
Чтобы найти всех соседей одной вершины $i$ , нужно проитерироваться по всей строке matrix[i], что занимает $O(V)$ времени, даже если у вершины всего один сосед.

Матрица смежности отлично подходит для плотных графов (Dense Graphs), где количество ребер стремится к максимуму ( $E \approx V^2$ ). Но в реальном мире и на собеседованиях такие графы встречаются редко. Социальная сеть из миллиона пользователей имеет $V = 10^6$ . Матрица для нее потребует триллион ячеек ( $10^{12}$ ), что займет терабайты оперативной памяти, хотя у среднего пользователя всего пара сотен друзей.

Список смежности (Adjacency List)

Чтобы не хранить пустоту, мы можем для каждой вершины запоминать только тех соседей, с которыми она реально связана.

Список смежности реализуется как массив списков или хеш-таблица, где ключ — это вершина, а значение — список ее прямых соседей: Map<Integer, List<Integer>>.

Преимущества:

Потребление памяти составляет строго $O(V + E)$ . Мы храним только существующие вершины и реальные связи между ними.
Поиск всех соседей вершины занимает время, пропорциональное количеству этих соседей. Если у узла 3 соседа, цикл выполнится 3 раза, а не $V$ раз.

Недостатки:

Проверка наличия конкретного ребра между $A$ и $B$ в худшем случае занимает $O(K)$ , где $K$ — количество соседей вершины $A$ . Приходится линейно сканировать список соседей.

Именно список смежности является стандартом де-факто для 95% графовых задач на LeetCode. Большинство графов в задачах — разреженные (Sparse Graphs), где $E$ значительно меньше $V^2$ .

Неявные графы (Implicit Graphs)

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

Классический пример — задачи на двумерных сетках (гридах), такие как поиск островов (Number of Islands) или выход из лабиринта. Вам дается матрица grid[m][n]. Здесь каждая ячейка — это вершина графа. А ребра неявно существуют между соседними по вертикали и горизонтали ячейками.

В неявных графах соседи вершины с координатами (r, c) вычисляются математически «на лету»: это (r-1, c), (r+1, c), (r, c-1) и (r, c+1). Достаточно проверить, не выходят ли эти координаты за границы сетки и не являются ли они препятствием. Выделение дополнительной памяти под список смежности здесь будет грубой ошибкой (Space-Time Trade-off не оправдан).

Как выбрать структуру: Читаем ограничения

В BigTech-интервью ожидается, что вы выберете структуру данных до написания кода, просто взглянув на раздел Constraints (ограничения) в описании задачи.

Посмотрите на $V$ (количество вершин). Если $V \leq 1000$ , то $V^2 \leq 10^6$ . Матрица смежности займет несколько мегабайт и инициализируется мгновенно. Можно использовать любой подход. Если $V = 10^5$ , то $V^2 = 10^{10}$ . Создание матрицы смежности немедленно приведет к ошибке Out of Memory (OOM) или Time Limit Exceeded (на инициализацию нулями уйдет слишком много времени). Только список смежности.
Оцените формат входных данных. Если на вход подан массив ребер edges — переводите его в список смежности. Если на вход подана матрица связей (например, задача Friend Circles, где M[i][j] = 1 означает дружбу) — граф уже представлен в виде матрицы смежности. Не тратьте время и память на конвертацию в список, работайте напрямую с M. Если дана двумерная карта (лабиринт) — используйте неявный граф, вычисляя соседей через сдвиги координат.

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

Алгоритм Дейкстры и BFS на графах: Поиск кратчайшего пути

Представьте, что вы стоите на перекрестке и открываете навигатор. Чтобы проложить маршрут до дома, программе нужно проанализировать миллионы возможных путей и выбрать оптимальный за доли секунды. Но что значит «оптимальный»? Если вы идете пешком, вас интересует наименьшее количество кварталов. Если едете на машине — наименьшее время с учетом пробок.

В прошлой главе мы научились представлять графы в памяти с помощью списков смежности и матриц. Теперь мы заставим эти структуры работать и ответим на главный вопрос маршрутизации: как найти кратчайший путь из точки А в точку Б?

Поиск в ширину (BFS) на графах: Когда важны только шаги

Вспомним главу о деревьях: алгоритм BFS (Breadth-First Search) исследует структуру поуровнево. Он идеально подходит для поиска кратчайшего пути, если «стоимость» перехода между любыми узлами одинакова (например, равна 1). Это называется невзвешенным графом (Unweighted Graph).

В графах, в отличие от деревьев, есть одна критическая особенность — циклы. Если в дереве мы всегда движемся от корня к листьям, то в графе мы можем бесконечно ходить по кругу $A \rightarrow B \rightarrow C \rightarrow A$ .

Чтобы BFS не зациклился, мы добавляем к стандартной структуре с очередью (Queue) паттерн отслеживания состояний — множество visited (Hash Set), которое мы обсуждали ранее.

Алгоритм BFS для поиска кратчайшего пути:

Помещаем стартовый узел в очередь и добавляем его в visited.
Пока очередь не пуста, извлекаем узел.
Перебираем всех его соседей по списку смежности.
Если сосед еще не в visited:
- Отмечаем его как посещенный.
- Запоминаем, откуда мы в него пришли (чтобы потом восстановить маршрут).
- Добавляем в очередь.

Поскольку очередь работает по принципу FIFO (First-In, First-Out), BFS гарантирует: мы сначала проверим все пути длиной в 1 шаг, затем все пути длиной в 2 шага и так далее. Первый раз, когда мы встречаем целевой узел, найденный путь к нему гарантированно является кратчайшим.

Проблема BFS: Когда у дорог появляется цена

BFS безупречен для лабиринтов или подсчета рукопожатий в социальной сети. Но вернемся к навигатору. Переход между перекрестками $A$ и $B$ может занимать 10 минут (пробка), а маршрут в объезд $A \rightarrow C \rightarrow B$ — всего 3 минуты (1 минута до $C$ и 2 минуты до $B$ ).

Граф, в котором ребра имеют числовое значение (расстояние, время, стоимость), называется взвешенным графом (Weighted Graph).

Если мы запустим обычный BFS на таком графе, он найдет путь $A \rightarrow B$ , потому что это всего 1 шаг. BFS измеряет длину пути количеством ребер, полностью игнорируя их вес. Нам нужен алгоритм, который измеряет длину пути суммой весов.

Алгоритм Дейкстры: Эволюция BFS

В 1956 году нидерландский ученый Эдсгер Вибе Дейкстра за 20 минут придумал алгоритм, который до сих пор работает в протоколах маршрутизации интернета (например, OSPF) и навигационных системах.

Эдсгер Вибе Дейкстра

Идея Дейкстры гениально проста. Если BFS использует обычную очередь (Queue) и всегда берет узел, который ближе всего по количеству шагов, давайте заменим очередь на очередь с приоритетом (Priority Queue / Min-Heap, которую мы разбирали в главе 9). Теперь мы будем всегда извлекать узел, который ближе всего по накопленной стоимости пути.

Как это работает на практике

Вместо того чтобы хранить в очереди просто узлы, мы будем хранить пары: (накопленная_стоимость, узел). Также нам понадобится хеш-таблица distances для хранения минимального известного расстояния от старта до каждого узла. Изначально расстояние до старта равно 0, а до всех остальных — бесконечности $\infty$ .

Шаги алгоритма Дейкстры:

Кладем в Min-Heap стартовый узел с весом 0: (0, Start).
Извлекаем из кучи узел с минимальной стоимостью. Назовем его current_node, а путь до него — current_cost.
Если мы уже находили путь к current_node дешевле, просто игнорируем его (это старая запись в куче).
Перебираем соседей current_node. Для каждого соседа считаем новый путь: $new\_cost = current\_cost + edge\_weight$
Релаксация (Relaxation): Если $new\_cost$ меньше, чем известное расстояние distances[neighbor], мы обновляем distances[neighbor] и добавляем (new_cost, neighbor) в Min-Heap.

Релаксация — это процесс улучшения (уменьшения) известного кратчайшего пути до узла, когда мы находим более выгодный маршрут через промежуточную вершину.

Оценка сложности алгоритма Дейкстры

Давайте проанализируем, сколько ресурсов потребляет алгоритм Дейкстры с использованием Min-Heap. Пусть $V$ — количество вершин, а $E$ — количество ребер в графе.

Временная сложность: $O(E \log V)$

В худшем случае каждое ребро графа заставит нас добавить новую запись в Min-Heap. Это $E$ операций вставки.
Максимальный размер кучи может достигать $V$ (или $E$ в плотных графах, но размер кучи влияет на логарифм, а $\log E \leq \log(V^2) = 2 \log V$ , константа 2 отбрасывается по правилам Big-O).
Извлечение минимального элемента и вставка в кучу стоят $O(\log V)$ .
Итого: $E$ раз выполняем операцию за $\log V$ , получаем $O(E \log V)$ .

Пространственная сложность: $O(V + E)$

Нам нужна память для хранения самого графа (список смежности) — $O(V + E)$ .
Массив/хеш-таблица расстояний distances занимает $O(V)$ .
Min-Heap в худшем случае хранит $O(V)$ элементов.

Ограничения: Чего боится Дейкстра?

Алгоритм Дейкстры построен на строгом жадном предположении: как только узел извлечен из Min-Heap, найденный путь к нему является окончательным и самым коротким.

Это предположение работает только в том случае, если все веса ребер неотрицательны ( $\geq 0$ ). Если в графе есть ребра с отрицательным весом (например, вы получаете бонус времени за проезд по определенной улице), алгоритм Дейкстры может выдать неверный результат. Он «зафиксирует» путь до узла, не подозревая, что длинный обходной маршрут с отрицательным ребром в итоге окажется дешевле. Для графов с отрицательными весами используются другие алгоритмы (например, алгоритм Беллмана-Форда), но на собеседованиях в BigTech в 95% случаев от вас ждут именно Дейкстру.

Резюме: Как выбрать алгоритм

При чтении условия задачи на LeetCode обращайте внимание на метрики пути:

Если просят найти кратчайший путь, и стоимость всех шагов равна (или нужно найти наименьшее количество действий) $\rightarrow$ BFS.
Если у переходов есть разная стоимость (время, деньги, дистанция), и она неотрицательна $\rightarrow$ Алгоритм Дейкстры (BFS + Min-Heap).

Система непересекающихся множеств (Union-Find) для задач на связность

Представьте, что вы разрабатываете бэкенд социальной сети. Пользователи ежесекундно добавляют друг друга в друзья. Вам поступает поток запросов: «Являются ли пользователь А и пользователь Б связанными через цепочку друзей?».

Мы уже знаем, что для поиска пути в графе можно использовать BFS или DFS. Но если граф меняется динамически (ребра добавляются постоянно), запускать обход за $O(V + E)$ на каждый запрос — значит положить сервер. Нам нужна структура данных, которая способна объединять вершины и отвечать на вопрос «связаны ли они?» практически за $O(1)$ .

Эта структура — Система непересекающихся множеств (Disjoint Set Union, DSU), также известная как паттерн Union-Find.

Анатомия DSU: Лес деревьев в одном массиве

Идея DSU элегантна: мы разбиваем все вершины графа на непересекающиеся множества (группы связности). В каждом множестве выбирается один «лидер» — корень. Если у двух вершин один и тот же лидер, значит, они находятся в одной компоненте связности.

Вместо сложных графовых структур DSU использует всего один массив parent. Значение parent[i] хранит родителя элемента $i$ . Если parent[i] == i, то элемент сам себе родитель, то есть он — корень (лидер) своего множества.

Структура поддерживает ровно две базовые операции:

Find(x) — найти лидера множества, в котором находится $x$ .
Union(x, y) — объединить множества, содержащие $x$ и $y$ .

Базовая реализация выглядит пугающе просто:

class DSU:
    def __init__(self, n):
        # Изначально каждый элемент — сам себе лидер
        self.parent = [i for i in range(n)]

    def find(self, x):
        # Идем вверх по дереву, пока не найдем корень
        while x != self.parent[x]:
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            # Подвешиваем корень одного к корню другого
            self.parent[root_y] = root_x

Проблема наивного подхода

Что произойдет, если мы последовательно вызовем Union(1, 2), Union(2, 3), Union(3, 4)? Корень 1 станет родителем 2, 2 станет родителем 3 и так далее. Наше дерево выродится в связный список (мы уже видели подобное в главе про бинарные деревья).

В таком случае операция Find будет занимать $O(N)$ времени. Чтобы достичь обещанной магии $O(1)$ , нам нужны две оптимизации.

Оптимизация 1: Сжатие пути (Path Compression)

Когда мы вызываем Find(x), мы проходим путь от узла $x$ до корня. Поскольку все узлы на этом пути принадлежат одному множеству, почему бы не сделать так, чтобы они все ссылались напрямую на корень?

Мы можем переписать Find рекурсивно. При возврате из рекурсии мы обновляем ссылку parent для каждого пройденного узла.

    def find(self, x):
        if self.parent[x] != x:
            # Рекурсивно находим корень и сразу переподвешиваем текущий узел
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

Теперь, если мы однажды потратили время на долгий Find, дерево «сплющивается». Все последующие вызовы для этих узлов будут работать за $O(1)$ .

Оптимизация 2: Объединение по рангу/размеру (Union by Size)

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

Для этого заведем массив size, который будет хранить количество элементов в дереве для каждого корня.

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n  # Изначально размер каждого дерева = 1

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False # Уже в одном множестве

        # Подвешиваем меньшее дерево к большему
        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        return True

Амортизационная магия: Обратная функция Аккермана

При использовании обеих оптимизаций (сжатие пути и объединение по размеру) амортизированная временная сложность операций Find и Union составляет $O(\alpha(N))$ .

$\alpha(N)$ — это обратная функция Аккермана. Она растет настолько медленно, что для любого мыслимого значения $N$ (даже превышающего количество атомов во Вселенной) $\alpha(N) \leq 5$ . Для всех практических задач на LeetCode и в реальной жизни можно считать, что DSU работает за константное время $O(1)$ .

Эвристика: Когда применять Union-Find на LeetCode

DSU — это узкоспециализированный, но невероятно мощный инструмент. Если в задаче просят найти кратчайший путь — это BFS. Если просят обойти все возможные состояния — это DFS. Но DSU сияет в следующих сценариях:

1. Подсчет компонент связности (Connected Components)

Классическая задача: Number of Connected Components in an Undirected Graph (LeetCode 323). Вместо того чтобы запускать DFS из каждой непосещенной вершины, мы можем использовать DSU. Изначально у нас $N$ компонент связности. Каждый раз, когда Union возвращает True (то есть мы успешно объединили два разных множества), мы уменьшаем счетчик компонент на 1.

2. Динамическая связность

Если ребра графа поступают по одному, и после каждого ребра нужно отвечать на вопросы о связности. DSU легко добавляет новые связи, в то время как матрица или список смежности потребовали бы перестроения или повторных обходов.

3. Поиск циклов в неориентированном графе

Задача Redundant Connection (LeetCode 684). Даны ребра дерева, к которому добавили одно лишнее ребро, создавшее цикл. Нужно найти это ребро. Идем по массиву ребер и делаем Union(u, v). Если перед объединением Find(u) == Find(v), значит, вершины уже соединены каким-то путем. Добавление текущего ребра замкнет цикл! Это ребро и есть ответ.

Ключевой инсайт: DSU не знает, как именно связаны узлы (он не хранит сам путь), он знает только факт их связи. Это идеальный пример принципа Space-Time Trade-off, где мы жертвуем информацией о топологии графа ради скорости ответа $O(1)$ .

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

Бинарный поиск: Не только по массиву, но и по ответу

Вы наверняка уже писали классический бинарный поиск: есть отсортированный массив чисел, нужно найти индекс заданного элемента за $O(\log N)$ . Это базовый навык. Но на собеседованиях в BigTech вас редко попросят просто найти число в массиве.

Чаще вы встретите задачи, где массива нет вообще, а вопрос звучит так: «Какова минимальная вместимость корабля, чтобы перевезти все грузы за D дней?» или «С какой минимальной скоростью нужно есть бананы, чтобы успеть до возвращения охранника?». В таких задачах пространство поиска огромно (например, от 1 до $10^9$ ), и линейный перебор приведет к Time Limit Exceeded. Здесь на сцену выходит паттерн Binary Search on Answer (Бинарный поиск по ответу).

Сдвиг парадигмы: От значений к предикатам

Чтобы применять бинарный поиск где угодно, нужно перестать думать о нем как о поиске конкретного числа. Бинарный поиск — это алгоритм поиска границы между двумя состояниями.

Представьте отсортированный массив: [10, 20, 30, 40, 50]. Нам нужно найти первое число, которое больше или равно 25. Вместо того чтобы смотреть на сами числа, применим к каждому элементу функцию-условие (предикат) $X \geq 25$ .

Массив чисел превращается в массив булевых значений:

Обратите внимание на важнейшее свойство: массив предикатов состоит из непрерывной серии False, за которой следует непрерывная серия True. Это называется монотонностью.

Если для какого-то элемента условие выполнилось (True), оно гарантированно выполнится для всех элементов правее. Если не выполнилось (False), оно точно не выполнится для всех элементов левее. Как только вы доказали монотонность пространства решений, вы можете использовать бинарный поиск для нахождения границы перехода от False к True.

Паттерн Binary Search on Answer

В задачах на поиск ответа мы ищем не индекс в массиве, а само значение ответа (например, скорость, вес, расстояние).

Признаки того, что задачу нужно решать через Binary Search on Answer:

В условии есть фразы-маркеры: «minimize the maximum» (минимизировать максимальное), «maximize the minimum» (максимизировать минимальное), «найти наименьшее $X$ , при котором возможно...».
Вы можете легко определить минимально и максимально возможный ответ (границы $L$ и $R$ ).
Если вы просто «угадаете» ответ $X$ , вы сможете легко и быстро (обычно за $O(N)$ ) проверить, валиден ли он.
Пространство ответов монотонно: если скорость $X$ достаточна для выполнения задачи, то любая скорость $X + 1$ и выше — тоже достаточна.

Разбор задачи: Koko Eating Bananas (LeetCode 875)

Обезьяна Коко любит бананы. Перед ней лежат $N$ стопок бананов, в $i$ -й стопке piles[i] бананов. У Коко есть $H$ часов до возвращения охранника. Коко может выбрать свою скорость поедания — $K$ бананов в час. Каждый час она выбирает одну стопку и съедает из нее $K$ бананов. Если в стопке меньше $K$ бананов, она съедает их все и больше ничего не ест в этот час (остаток часа отдыхает). Задача: найти минимальную скорость $K$ , при которой Коко успеет съесть все бананы за $H$ часов.

Шаг 1: Определяем пространство поиска (L и R)

Какова минимально возможная скорость? Коко должна есть хотя бы 1 банан в час. Значит, $L = 1$ . Какова максимальная осмысленная скорость? Если она будет есть со скоростью, равной размеру самой большой стопки, она будет тратить ровно 1 час на каждую стопку. Есть еще быстрее нет смысла — она все равно не может начать новую стопку в тот же час. Значит, $R = \max(\text{piles})$ .

Шаг 2: Пишем функцию-предикат

Нам нужна функция canEatAll(piles, H, K), которая отвечает на вопрос: «Если скорость равна $K$ , успеет ли Коко за $H$ часов?».

Для каждой стопки время поедания вычисляется как деление с округлением вверх: $\lceil \frac{\text{pile}}{K} \rceil$ . В коде на целочисленной арифметике это часто записывают как (pile + K - 1) / K или используют встроенные математические функции.

Мы суммируем часы для всех стопок. Если итоговая сумма $\leq H$ , функция возвращает True. Эта проверка занимает $O(N)$ времени.

Шаг 3: Запускаем бинарный поиск

Мы берем среднюю скорость $mid$ между $L$ и $R$ и проверяем ее через предикат.

Логика сужения границ:

Если canEatAll(mid) вернуло True, значит, скорость $mid$ подходит. Но мы ищем минимальную скорость. Возможно, Коко справится и медленнее. Мы отбрасываем правую половину и сохраняем $mid$ как возможный ответ: $R = mid$ .
Если canEatAll(mid) вернуло False, значит, Коко не успевает. Скорость $mid$ и все скорости меньше нее нам не подходят. Мы обязаны увеличить скорость: $L = mid + 1$ .

def minEatingSpeed(piles, H):
    # L и R - это не индексы массива, а значения скорости!
    L = 1
    R = max(piles)

    while L < R:
        mid = L + (R - L) // 2

        # Вычисляем суммарное время при скорости mid
        hours_spent = 0
        for pile in piles:
            import math
            hours_spent += math.ceil(pile / mid)

        if hours_spent <= H:
            # Успеваем. Пробуем найти скорость еще меньше.
            R = mid
        else:
            # Не успеваем. Нужно есть быстрее.
            L = mid + 1

    return L # Когда L == R, мы нашли минимальную валидную скорость

Оценка сложности алгоритма

В классическом бинарном поиске по массиву сложность составляет $O(\log N)$ . В паттерне Binary Search on Answer формула меняется, потому что на каждом шаге мы вызываем функцию-предикат.

Итоговая временная сложность вычисляется как:

O(T \cdot \log M)

Где:

$M$ — размер пространства поиска (разница между $R$ и $L$ ). В нашем случае $M = \max(\text{piles})$ . Количество шагов бинарного поиска равно $\log M$ .
$T$ — время выполнения функции-предиката. В задаче про бананы мы проходим по массиву из $N$ стопок, поэтому $T = O(N)$ .

Итоговая сложность для Koko Eating Bananas: $O(N \log M)$ . Пространственная сложность (память): $O(1)$ , так как мы храним только несколько переменных-указателей и не выделяем новых структур данных.

Шаблон для границ и избегание бесконечных циклов

Самая частая ошибка на собеседованиях при написании бинарного поиска — это бесконечный цикл (Time Limit Exceeded), когда $L$ и $R$ застревают на соседних числах.

Чтобы этого избежать, используйте стандартизированный шаблон:

Цикл всегда while L < R (строго меньше).
Вычисление середины: $mid = L + \frac{R - L}{2}$ . Это предотвращает целочисленное переполнение (Integer Overflow) в языках вроде Java/C++, в отличие от наивного $(L + R) / 2$ .
Если $mid$ удовлетворяет условию и мы ищем минимум, сдвигаем правую границу: $R = mid$ . Мы не пишем $R = mid - 1$ , потому что текущий $mid$ может оказаться тем самым правильным ответом.
Если $mid$ не удовлетворяет условию, сдвигаем левую границу: $L = mid + 1$ . Мы точно знаем, что $mid$ — ошибочный ответ, поэтому смело исключаем его.

Когда цикл завершится, $L$ и $R$ будут указывать на одно и то же число — это и есть искомая граница перехода состояний.

Паттерн K-way Merge: Слияние нескольких отсортированных структур

Слияние двух отсортированных массивов с помощью двух указателей требует $O(N)$ времени. Если у нас есть $K$ массивов, наивный подход — сливать их попарно или добавить все элементы в один массив и отсортировать за $O(N \log N)$ . Но когда структуры уже отсортированы внутри себя, мы можем использовать паттерн K-way Merge, чтобы снизить время до $O(N \log K)$ , а потребление памяти — до $O(K)$ .

В основе этого паттерна лежит Min-Heap, с которым мы познакомились при поиске Top-K элементов. Однако теперь куча хранит не просто значения, а контекст — информацию о том, откуда пришло значение и где искать следующее.

Анатомия контекстного кортежа

При работе со связными списками узел сам по себе содержит ссылку next. Но при слиянии массивов или строк матрицы извлечение минимального элемента из кучи оставляет нас вслепую: мы знаем минимальное значение, но не знаем, из какого массива оно взято, чтобы положить в кучу следующий элемент на замену.

Паттерн K-way Merge решает это упаковкой данных в кортеж (Tuple) из трех элементов:

value — само значение (по нему куча выполняет сортировку).
list_index — индекс массива/строки, из которого взято значение.
element_index — индекс самого элемента внутри этого массива.

Цикл работы паттерна всегда одинаков:

Инициализация: кладем в Min-Heap первые элементы из всех $K$ структур (кортежи вида (value, i, 0)).
Извлекаем минимальный кортеж из кучи.
Добавляем извлеченное value в результирующий массив (или обновляем счетчик).
Проверяем, есть ли в массиве list_index следующий элемент (по индексу element_index + 1). Если есть — формируем новый кортеж и пушим его в кучу.
Повторяем, пока куча не опустеет или мы не найдем нужный по счету элемент.

Поиск K-го элемента в отсортированной матрице

Рассмотрим задачу K-th Smallest Element in a Sorted Matrix. Дана матрица $N \times N$ , где каждая строка и каждый столбец отсортированы по возрастанию. Нужно найти $K$ -й по величине элемент во всей матрице.

Мы не можем просто взять элемент по координатам, так как глобальный порядок между строками не гарантирован. Элемент matrix[0][2] может быть как больше, так и меньше matrix[1][0]. Но мы можем рассматривать эту матрицу как $N$ отсортированных массивов (строк).

Алгоритм:

Размер нашей кучи будет равен $N$ (количеству строк).
Мы помещаем в Min-Heap первые элементы каждой строки.
Делаем $K - 1$ итераций извлечения минимума. На каждой итерации мы берем минимальный элемент, смотрим на его list_index (номер строки) и element_index (номер столбца), и кладем в кучу соседа справа: element_index + 1.
На $K$ -й итерации корень кучи будет содержать искомый ответ.

Сложность такого решения: $O(X \log N)$ для инициализации кучи (где $X = \min(N, K)$ ) плюс $K$ итераций извлечения и вставки, каждая за $O(\log X)$ . Итоговое время $O(K \log X)$ . Это значительно быстрее полной сортировки матрицы, особенно если $K$ невелико.

Smallest Range: Слияние с отслеживанием максимума

Паттерн K-way Merge раскрывает свою истинную силу в задачах, где нужно анализировать элементы из разных групп одновременно. Классический пример — задача Smallest Range Covering Elements from K Lists.

Дано $K$ отсортированных списков целых чисел. Нужно найти наименьший диапазон $[L, R]$ , который включает хотя бы одно число из каждого списка. Если есть несколько диапазонов одинаковой длины, выбирается тот, у которого $L$ меньше.

Пример: Список 1: [4, 10, 15, 24, 26] Список 2: [0, 9, 12, 20] Список 3: [5, 18, 22, 30]

Чтобы диапазон покрывал все списки, он должен начинаться с какого-то элемента и заканчиваться каким-то элементом, при этом между ними (включительно) должны оказаться представители всех $K$ массивов.

Как здесь помогает K-way Merge? Мы можем поддерживать "окно" из $K$ элементов — по одному от каждого списка.

Инициализируем Min-Heap первыми элементами всех $K$ списков.
Текущий диапазон $[L, R]$ определяется просто: $L$ — это минимум в нашем окне (корень Min-Heap), а $R$ — это максимум в нашем окне.
Чтобы уменьшить диапазон, нам нужно сдвинуть левую границу вправо. Мы извлекаем минимум из кучи и заменяем его следующим элементом из того же списка.

Проблема: Min-Heap дает нам $L$ за $O(1)$ , но как быстро находить $R$ (максимум среди текущих $K$ элементов)? Решение: Нам не нужна Max-Heap. Мы можем просто поддерживать переменную current_max. При инициализации мы находим максимальный из первых элементов. Далее, каждый раз, когда мы достаем новый элемент из списка и пушим его в кучу, мы обновляем current_max = max(current_max, new_value).

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

Временная сложность этого алгоритма составляет $O(N \log K)$ , где $N$ — общее количество элементов во всех списках. Пространственная сложность строго ограничена размером кучи — $O(K)$ .

Паттерн K-way Merge — это мост между локальной отсортированностью и глобальным порядком. Всякий раз, когда задача требует найти пересечение, диапазон или конкретный ранг среди нескольких отсортированных потоков данных, упаковка контекста в Min-Heap становится самым элегантным решением.

Сортировка подсчетом и поразрядная сортировка: Когда O(N log N) слишком медленно

В информатике существует строгое математическое доказательство: любой алгоритм сортировки, основанный на сравнении элементов (например, QuickSort или MergeSort), не может работать быстрее, чем за время $O(N \log N)$ . Это фундаментальный барьер. Кажется, что быстрее отсортировать массив невозможно.

Но что, если нам нужно отсортировать базу данных из 10 миллионов пользователей по возрасту (от 0 до 120 лет)? Использование $O(N \log N)$ здесь избыточно. Мы можем обойти математический барьер и отсортировать данные за линейное время $O(N)$ , если вообще откажемся от сравнения элементов между собой.

Сортировка подсчетом (Counting Sort): Индекс как значение

В главе про оценку памяти мы разбирали паттерн Index Mapping, где значение элемента используется как индекс массива. Сортировка подсчетом возводит эту идею в абсолют.

Вместо того чтобы спрашивать «какое из двух чисел больше?», алгоритм просто подсчитывает, сколько раз каждое число встречается во входных данных.

Алгоритм состоит из трех шагов:

Поиск диапазона: Находим минимальное и максимальное значения в массиве, чтобы создать массив частот нужного размера.
Подсчет (Frequency Map): Проходим по исходному массиву. Если видим число X, увеличиваем значение в массиве частот по индексу X на единицу.
Сборка: Проходим по массиву частот слева направо (от меньших индексов к большим) и записываем индексы обратно в результат столько раз, сколько указано в ячейке.

Сортировка подсчетом не перемещает элементы, сравнивая их. Она уничтожает исходный массив и генерирует новый, правильный массив с нуля, опираясь на карту частот.

Анализ сложности этого подхода сильно отличается от классических сортировок. Время выполнения составляет $O(N + K)$ , где $N$ — количество элементов, а $K$ — размер диапазона значений (разница между максимумом и минимумом). Пространственная сложность равна $O(K)$ , так как нам нужен дополнительный массив для частот.

Здесь кроется главная уязвимость алгоритма.

Если входной массив состоит всего из двух чисел: [1, 1000000000], сортировка подсчетом попытается выделить память под массив частот размером в миллиард элементов. Это приведет к ошибке Memory Limit Exceeded. Сортировка подсчетом идеально работает только для плотных данных с небольшим разбросом значений (возраст, оценки, RGB-коды пикселей).

Поразрядная сортировка (Radix Sort): Разделяй и властвуй над разрядами

Чтобы обойти проблему огромного потребления памяти при большом разбросе чисел, мы перестаем смотреть на число как на единое целое. Вместо этого мы рассматриваем его как последовательность цифр (разрядов).

Поразрядная сортировка (Radix Sort) сортирует числа по одной цифре за раз, начиная с младшего разряда (единиц) и заканчивая старшим. Для сортировки каждого отдельного разряда используется алгоритм, который работает за $O(N)$ — чаще всего это модифицированная сортировка подсчетом, где диапазон $K$ всегда равен 10 (цифры от 0 до 9).

Механика работы:

Берем младший разряд всех чисел (единицы).
Распределяем числа по 10 «корзинам» (от 0 до 9) в зависимости от этой цифры.
Собираем числа обратно в массив: сначала все из корзины 0, затем из корзины 1 и так далее.
Повторяем процесс для десятков, затем для сотен, пока не закончатся разряды у самого длинного числа.

Критически важное свойство, без которого Radix Sort развалится — базовая сортировка разрядов должна быть устойчивой (Stable Sort).

Устойчивая сортировка гарантирует, что если два элемента имеют одинаковый ключ сортировки, они сохранят свой первоначальный относительный порядок в итоговом массиве.

Временная сложность Radix Sort составляет $O(d \cdot (N + b))$ , где $d$ — максимальное количество разрядов в самом длинном числе, а $b$ — основание системы счисления (обычно 10). Поскольку $d$ и $b$ для 32-битных целых чисел являются небольшими константами (максимум 10 цифр), алгоритм фактически работает за линейное время $O(N)$ .

Как распознать эти алгоритмы на LeetCode

В задачах BigTech вас редко попросят просто «реализовать сортировку подсчетом». Эти алгоритмы скрываются за специфическими ограничениями (Constraints) в условии задачи.

Признак 1: Огромный массив, но крошечный диапазон значений Если вы видите в условии:

1 <= nums.length <= 10^5
0 <= nums[i] <= 100 Это кричащий сигнал для сортировки подсчетом. Классический пример — задача Sort Colors (LeetCode 75), где массив состоит только из чисел 0, 1 и 2. Вместо $O(N \log N)$ вы можете просто посчитать количество нулей, единиц и двоек за один проход, а затем перезаписать массив.

Признак 2: Требование линейного времени на неотсортированных данных Задача Maximum Gap (LeetCode 164) просит найти максимальную разницу между последовательными элементами в отсортированном виде. Но условие жестко требует: алгоритм должен работать за линейное время $O(N)$ и использовать линейную память. Ограничения: 1 <= nums.length <= 10^5, 0 <= nums[i] <= 10^9. Диапазон значений до миллиарда исключает обычную сортировку подсчетом (не хватит памяти), а требование $O(N)$ исключает Arrays.sort(). Оптимальным решением здесь выступает Radix Sort, который элегантно справляется с большими числами за линейное время.

Линейные сортировки — это мощный инструмент оптимизации, который работает там, где данные имеют предсказуемую структуру или ограниченный алфавит. Они завершают наш арсенал базовых алгоритмов трансформации коллекций.

Поиск подстрок: Алгоритмы KMP и Rabin-Karp на практике

Представьте, что вам нужно найти конкретную мутацию длиной в 10 000 нуклеотидов внутри генома человека, состоящего из 3 миллиардов пар оснований. Наивный поиск (прикладывать паттерн к каждой позиции текста) потребует $3 \times 10^{13}$ сравнений символов. Компьютер будет выполнять это минуты, а при множественных запросах — часы.

В предыдущих главах мы использовали паттерн Sliding Window для оптимизации вложенных циклов и хеш-таблицы для поиска за $O(1)$ . Сегодня мы объединим эти идеи, чтобы научиться находить подстроку длины $M$ в тексте длины $N$ за строго линейное время $O(N + M)$ . Для этого в арсенале BigTech есть два фундаментальных подхода: Rabin-Karp и алгоритм Кнута-Морриса-Пратта (KMP).

Алгоритм Rabin-Karp: Sliding Window встречает Hashing

Наивный поиск медленный, потому что при сдвиге окна на один символ мы заново сравниваем всю строку. Алгоритм Rabin-Karp предлагает элегантный выход: давайте сравнивать не сами строки, а их хеши.

Если хеш искомого паттерна равен хешу текущего окна в тексте, мы посимвольно проверяем совпадение (чтобы исключить коллизию). Если хеши не равны, строки точно разные — идем дальше.

Но если вычислять хеш окна с нуля на каждом шаге, мы снова получим сложность $O(N \times M)$ . Здесь на сцену выходит Rolling Hash (скользящий хеш).

Механика Rolling Hash

Идея Rolling Hash в том, чтобы вычислить хеш нового окна за $O(1)$ , используя значение предыдущего окна. Мы рассматриваем строку как число в системе счисления с основанием $B$ (обычно размер алфавита, например, 256) по модулю большого простого числа $P$ (чтобы избежать переполнения).

При сдвиге окна вправо на один символ нам нужно:

Вычесть влияние символа, который выпал из окна слева.
Сдвинуть оставшиеся символы на один разряд влево (умножить на $B$ ).
Прибавить значение нового символа, вошедшего справа.

Формула пересчета выглядит так: $H_{new} = (H_{old} - char_{out} \times B^{M-1}) \times B + char_{in}$

Где:

$H_{old}$ — хеш предыдущего окна.
$char_{out}$ — ASCII-код символа, покинувшего окно.
$B^{M-1}$ — вес старшего разряда (вычисляется один раз заранее).
$char_{in}$ — ASCII-код нового символа.
Все операции выполняются по модулю $P$ .

Ограничения Rabin-Karp

Rabin-Karp отлично справляется с поиском множества паттернов одновременно (например, в системах антиплагиата), так как мы можем хранить хеши всех паттернов в Hash Set.

Однако у него есть уязвимость: коллизии. Если злоумышленник подберет текст так, что каждое окно будет давать тот же хеш, что и паттерн, алгоритму придется выполнять посимвольное сравнение на каждом шаге. Временная сложность деградирует до $O(N \times M)$ . Когда нужен гарантированный результат без оглядки на коллизии, используют KMP.

Алгоритм KMP: Память о прошлых совпадениях

Алгоритм Кнута-Морриса-Пратта (KMP) решает проблему наивного поиска иначе. Он задает вопрос: "Если мы совпали на 5 символах, а на 6-м ошиблись, зачем нам возвращать указатель текста назад?"

Мы уже изучили часть паттерна. KMP использует знания о самом паттерне, чтобы при несовпадении сдвинуть его вправо на максимально возможное безопасное расстояние, не возвращая указатель в тексте.

Префикс-функция и массив LPS

Сердце KMP — это массив LPS (Longest Prefix Suffix). Для каждого индекса $i$ в паттерне он хранит длину самого длинного собственного префикса, который одновременно является суффиксом для подстроки от $0$ до $i$ .

Звучит сложно, разберем на примере паттерна ABABC:

A -> префиксов нет. LPS = 0.
AB -> префикс A, суффикс B. Не равны. LPS = 0.
ABA -> префикс A, суффикс A. Равны! Длина 1. LPS = 1.
ABAB -> префикс AB, суффикс AB. Равны! Длина 2. LPS = 2.
ABABC -> суффикс заканчивается на C, таких префиксов нет. LPS = 0.

Итоговый массив LPS для ABABC равен [0, 0, 1, 2, 0].

Как KMP использует LPS

Допустим, мы ищем паттерн ABABC в тексте ABABDABABC. Мы сравниваем символы, и на 4-м индексе происходит несовпадение (в тексте D, в паттерне C).

В наивном алгоритме мы бы сдвинули паттерн на 1 позицию вправо и начали всё с нуля. Но посмотрите на уже совпавшую часть: ABAB. Массив LPS говорит нам, что у строки ABAB есть префикс AB, который равен её суффиксу. Это значит, что нам не нужно проверять эти два символа заново! Мы можем просто сдвинуть паттерн так, чтобы его префикс AB встал на место суффикса AB, который мы только что прочитали в тексте.

Указатель в тексте $i$ никогда не возвращается назад. Он либо стоит на месте (пока паттерн сдвигается по LPS), либо идет вперед. Именно это гарантирует строгую сложность $O(N)$ .

Шаблон реализации KMP на Python

Разделение на две функции делает код чище и показывает интервьюеру, что вы понимаете архитектуру алгоритма.

def compute_lps(pattern: str) -> list[int]:
    M = len(pattern)
    lps = [0] * M
    length = 0  # длина предыдущего самого длинного префикс-суффикса
    i = 1

    while i < M:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # Откатываемся к предыдущему известному префиксу
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text: str, pattern: str) -> int:
    if not pattern: return 0

    N, M = len(text), len(pattern)
    lps = compute_lps(pattern)

    i = 0  # индекс для text
    j = 0  # индекс для pattern

    while i < N:
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == M:
            return i - j  # Нашли совпадение
            # Если нужно найти все вхождения: j = lps[j - 1]

        elif i < N and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]  # Магия KMP: сдвиг без возврата i
            else:
                i += 1

    return -1

Стратегия выбора: Что применять на LeetCode?

Критерий	Rabin-Karp	KMP
Временная сложность	Средняя $O(N + M)$ , Худшая $O(N \times M)$	Строго гарантированная $O(N + M)$
Сложность реализации	Проще (особенно если помните модульную арифметику)	Сложнее (легко ошибиться в индексах LPS)
Множественный поиск	Идеален (ищем 100 паттернов за один проход текста)	Не подходит (нужен алгоритм Ахо-Корасик)
Двумерный поиск	Возможен (2D Rolling Hash)	Неприменим

Совет для интервью: Если задача требует просто найти подстроку (например, LeetCode 28: Find the Index of the First Occurrence in a String), в Python достаточно использовать встроенный text.find(pattern), который работает на оптимизированном алгоритме Бойера-Мура-Хорспула.

Однако, если задача связана со свойствами самой строки (например, LeetCode 214: Shortest Palindrome или LeetCode 686: Repeated String Match), интервьюер ожидает именно KMP, так как массив LPS содержит информацию о внутренней симметрии строки, которую невозможно получить хешированием.

В следующей главе мы рассмотрим структуру данных Trie (Префиксное дерево), которая позволяет эффективно искать слова в огромных словарях и реализовывать системы автодополнения (Autocomplete).

Префиксное дерево (Trie): Эффективный автокомплит и поиск слов

В прошлой главе мы разобрали алгоритм KMP, который блестяще решает задачу поиска одного паттерна в длинном тексте. Но что если задача вывернута наизнанку? У вас есть словарь из миллиона слов, и пользователь вводит строку в строку поиска. Нужно мгновенно найти все слова, начинающиеся на "auto".

Обычная хеш-таблица (Hash Set) здесь бессильна: она проверяет только точные совпадения за $O(1)$ . Чтобы найти префикс в хеш-таблице, придется перебрать все миллион ключей, что даст $O(N \times L)$ , где $N$ — количество слов, а $L$ — длина слова.

Для таких задач существует специализированная структура данных — Префиксное дерево (Trie, читается как "трай").

Анатомия префиксного дерева

Trie — это $N$ -арное дерево, в котором узлы не хранят сами слова. Вместо этого путь от корня до узла определяет строку.

Каждое ребро (или указатель на потомка) представляет собой один символ. Корень дерева всегда пуст. Если мы хотим добавить слово "cat", мы создаем путь от корня: c $\rightarrow$ a $\rightarrow$ t.

Ключевая особенность Trie — переиспользование общих префиксов. Если после "cat" мы добавим "car", дерево не будет создавать новую ветку с нуля. Оно пройдет по существующим c $\rightarrow$ a, и только на последнем шаге создаст новое ответвление r.

Важнейший элемент каждого узла — булевый флаг is_end_of_word. Без него невозможно отличить, является ли текущий путь полноценным словом или только префиксом. Например, если в словаре есть слова "car" и "cart", узел r будет иметь is_end_of_word = True, но при этом у него будет потомок t, который тоже будет отмечен как конец слова.

Реализация узла в памяти

На практике узел Trie реализуется двумя способами в зависимости от ограничений задачи:

Массив фиксированного размера (Array-based): Если мы точно знаем, что словарь состоит только из строчных английских букв, потомки хранятся как массив из 26 элементов. Индекс вычисляется как смещение ASCII-кода: char - 'a'. Это дает абсолютно жесткое $O(1)$ для перехода, но потребляет много памяти, так как большинство ячеек массива будут пустыми (Null).
Хеш-таблица (Map-based): Потомки хранятся в структуре Map<Character, TrieNode>. Это экономит память на разреженных ветвях и поддерживает любой набор символов (весь Unicode), но добавляет накладные расходы на вычисление хеша при каждом переходе.

Оценка сложности: независимость от объема словаря

Главная магия Trie раскрывается при анализе асимптотической сложности.

Время поиска и вставки: $O(L)$ , где $L$ — длина искомого или вставляемого слова. Обратите внимание: в формуле нет $N$ (количества слов в словаре). Поиск слова длиной 5 символов займет 5 операций, независимо от того, лежит в дереве сто слов или десять миллионов.

Пространственная сложность: В худшем случае, когда слова вообще не имеют общих префиксов, дерево займет $O(N \times L)$ памяти. Однако на реальных языковых данных (английский язык, логи серверов, URL-адреса) слова сильно пересекаются. Trie выступает как алгоритм сжатия, объединяя общие начала строк.

Паттерн 1: Автокомплит (Поиск по префиксу)

Классическая задача на системный дизайн и алгоритмы — Design Search Autocomplete System. Как вернуть топ вариантов продолжения введенного текста?

Алгоритм работы с Trie делится на две фазы:

Спуск по префиксу: Начиная от корня, мы идем по символам введенного префикса. Если на каком-то шаге нужного потомка нет — автокомплит возвращает пустой список. Если мы успешно дошли до конца префикса, мы оказываемся в узле, от которого растут все возможные продолжения.
Сбор слов (DFS): Из найденного узла запускается стандартный поиск в глубину (DFS), который мы разбирали при изучении деревьев. Мы обходим все дочерние ветви, накапливая символы в строку. Каждый раз, когда мы встречаем узел с is_end_of_word == True, мы добавляем накопленную строку в итоговый список.

Паттерн 2: Word Search II (Trie + DFS на сетке)

Это одна из самых известных задач уровня Hard на LeetCode (№212), которая идеально демонстрирует синергию пройденных нами тем: неявных графов, DFS и префиксных деревьев.

Условие: Дана матрица букв $M \times N$ и список слов. Нужно найти все слова из списка, которые можно собрать на матрице, двигаясь по горизонтали и вертикали (одна ячейка используется в слове не более одного раза).

Наивный подход: Для каждого слова из списка запускать DFS по всей матрице. Сложность будет катастрофической: $O(W \times C \times 3^L)$ , где $W$ — количество слов, $C$ — количество ячеек в матрице, $L$ — длина слова (на каждом шаге DFS у нас 3 направления, так как назад идти нельзя).

Оптимизация с Trie: Вместо того чтобы искать каждое слово по отдельности, мы инвертируем логику. Мы строим Trie из всех искомых слов. Затем мы запускаем DFS из каждой ячейки матрицы один раз, параллельно спускаясь по нашему Trie.

Если текущей буквы матрицы нет среди потомков текущего узла Trie — мы немедленно прерываем DFS (отсечение ветви). Нет смысла исследовать этот путь дальше, ни одно слово в словаре так не начинается.
Если буква есть, мы переходим в следующего потомка Trie и продолжаем DFS на матрице.
Если в узле Trie установлен флаг is_end_of_word, мы нашли слово.

Трюк для ускорения: Удаление найденных слов

В задачах типа Word Search II есть скрытая проблема. Если в матрице много путей образуют одно и то же слово, наш DFS найдет его несколько раз. Кроме того, после нахождения слова нам больше не нужно искать его в других частях матрицы.

Чтобы радикально ускорить алгоритм, сразу после того как слово найдено (сработал is_end_of_word), мы меняем этот флаг на False. Более того, если у этого узла больше нет других потомков, мы можем удалить сам узел из дерева, чтобы будущие обходы DFS обрывались еще раньше.

Префиксное дерево — это мост между строковыми алгоритмами и обходами графов. Превращая плоские строки в иерархическую структуру, мы получаем возможность применять мощь DFS для лексикографического поиска и отсечения тупиковых маршрутов за $O(1)$ .

Жадные алгоритмы: Когда локальный оптимум ведет к глобальному

Представьте, что вы работаете кассиром и вам нужно выдать покупателю сдачу в 87 центов. Перед вами лежат монеты номиналом 50, 25, 10, 5 и 1. Как вы поступите? Вы не будете строить в уме дерево всех возможных комбинаций. Вы просто возьмете самую крупную монету, которая меньше 87 (это 50). Останется 37. Снова берете самую крупную (25). Остается 12. Берете 10. Остается 2. Берете две по 1.

Вы только что применили жадный алгоритм. На каждом шаге вы принимали решение, которое казалось наилучшим прямо сейчас (взять максимальный номинал), совершенно не задумываясь о том, как это повлияет на следующие шаги. И в случае с реальными деньгами эта стратегия безотказно приводит к идеальному результату — минимальному количеству монет.

Иллюзия простоты и главная ловушка

Суть жадного алгоритма заключается в одном правиле: локальный оптимум должен вести к глобальному оптимуму. Мы делаем лучший выбор здесь и сейчас, отрезаем все остальные варианты и двигаемся дальше. Благодаря этому жадные алгоритмы работают невероятно быстро — обычно за $O(N)$ или $O(N \log N)$ (если требуется предварительная сортировка).

Но у этой скорости есть цена. Жадный алгоритм слеп.

Давайте изменим правила игры. Допустим, в вымышленной стране есть монеты номиналом 1, 3 и 4. Вам нужно выдать сдачу в 6. Если вы примените жадный алгоритм, вы возьмете самую крупную монету — 4. Останется 2. Вы выдадите их двумя монетами по 1. Итого: 3 монеты (4, 1, 1). Но оптимальный ответ — 2 монеты (3 и 3).

Жадный подход провалился. Приняв локально лучшее решение (взять 4), мы загнали себя в ветку, где глобальный оптимум недостижим. Жадные алгоритмы работают только для тех задач, которые обладают математическим «свойством жадного выбора» (Greedy Choice Property). Если его нет — алгоритм выдаст красивый, быстрый, но неправильный ответ.

В задачах BigTech жадные алгоритмы чаще всего встречаются в двух базовых паттернах. Разберем их на практике.

Паттерн 1: Сортировка + Жадный выбор

Часто данные изначально перемешаны так, что локальный оптимум не очевиден. Но стоит их отсортировать, как правильный выбор на каждом шаге становится тривиальным.

Классический пример — задача Assign Cookies (LeetCode 455). У вас есть массив детей, где каждое число — это фактор жадности ребенка (минимальный размер печенья, который его устроит). И есть массив печений с их размерами. Нужно накормить максимальное количество детей. Одному ребенку — одно печенье.

Жадная стратегия:

Отсортировать детей по возрастанию аппетита.
Отсортировать печенья по возрастанию размера.
Брать самого «нетребовательного» ребенка и давать ему самое маленькое печенье, которое ему подходит.

Почему это работает? Если маленькое печенье может удовлетворить ребенка с маленьким аппетитом, нет смысла отдавать ему большое печенье — большое пригодится для более требовательного ребенка. Мы ничего не теряем, делая такой выбор.

def findContentChildren(g, s):
    g.sort() # Аппетиты детей
    s.sort() # Размеры печений

    child_i = 0
    cookie_i = 0

    while child_i < len(g) and cookie_i < len(s):
        if s[cookie_i] >= g[child_i]:
            # Печенье подходит! Ребенок доволен, переходим к следующему
            child_i += 1
        # В любом случае переходим к следующему печенью
        # (если не подошло этому ребенку, оно слишком маленькое для всех остальных)
        cookie_i += 1

    return child_i

Сложность здесь диктуется сортировкой: $O(N \log N + M \log M)$ . Сам проход двумя указателями занимает линейное время.

Паттерн 2: Динамическая граница (Без сортировки)

Второй тип жадных задач не требует сортировки. Вместо этого мы проходим по массиву и на каждом шаге «жадно» обновляем какую-то глобальную границу или состояние.

Ярчайший пример — Jump Game (LeetCode 55). Дан массив nums, где каждое число означает максимальную длину прыжка из этой позиции. Вы начинаете с индекса 0. Можно ли добраться до последнего индекса?

Пример: nums = [2, 3, 1, 1, 4] Если пытаться симулировать все возможные прыжки (из 2 прыгнуть на 1 шаг, потом оттуда еще куда-то, потом вернуться и прыгнуть на 2 шага...) — мы получим дерево вариантов и сложность $O(2^N)$ . Для $N = 10^4$ это гарантированный Time Limit Exceeded.

Вместо симуляции путей применим жадный подход: давайте просто отслеживать самую дальнюю точку, до которой мы в принципе можем дотянуться на данный момент.

Алгоритм предельно прост:

Заводим переменную farthest = 0.
Идем по массиву слева направо.
Если текущий индекс i больше, чем farthest — значит, мы застряли. Мы физически не можем сюда допрыгнуть. Возвращаем False.
Иначе жадно обновляем границу: farthest = max(farthest, i + nums[i]).
Если farthest достиг или превысил последний индекс — мы победили.

def canJump(nums):
    farthest = 0
    for i in range(len(nums)):
        # Если текущая клетка недостижима — дальше пути нет
        if i > farthest:
            return False

        # Жадно расширяем границу достижимости
        farthest = max(farthest, i + nums[i])

        # Ранний выход: если уже можем допрыгнуть до конца
        if farthest >= len(nums) - 1:
            return True

    return True

Сложность: $O(N)$ по времени и $O(1)$ по памяти. Мы сжали экспоненциальное дерево решений до одного линейного прохода.

Как распознать жадный алгоритм на собеседовании?

Если вы видите задачу на поиск максимума/минимума или проверку возможности («можно ли дойти...»), обратите внимание на Constraints (ограничения):

Если $N = 10^5$ , алгоритм со сложностью $O(N^2)$ не пройдет. Это мощнейшая подсказка. Задача решается либо жадно за $O(N)$ или $O(N \log N)$ , либо бинарным поиском по ответу.
Попробуйте найти контрпример. Можете ли вы придумать ситуацию, где очевидный лучший шаг сейчас приведет к катастрофе потом? Если после 3-5 минут раздумий контрпример не находится — скорее всего, перед вами жадный алгоритм.

Но что делать, если контрпример нашелся? Что, если локальный оптимум действительно отрезает путь к глобальному, как в примере с монетами [1, 3, 4]? В таких случаях мы не можем слепо выбрать один путь. Нам нужно исследовать разные варианты, но делать это умно, не пересчитывая одно и то же дважды. Именно для этого был изобретен мощнейший инструмент алгоритмики — Динамическое Программирование, к которому мы перейдем в следующей главе.

Введение в Динамическое Программирование: Мемоизация vs Табуляция

В прошлой главе мы остановились на уязвимости жадных алгоритмов. Представьте, что вам нужно выдать сдачу в 6 условных единиц монетами номиналом 1, 3 и 4. Жадный алгоритм берет самую крупную монету (4), а затем две по 1. Итого — 3 монеты. Но правильный ответ — две монеты по 3. Жадный подход провалился, потому что принял локально оптимальное решение, отрезав себе путь к глобальному оптимуму.

Чтобы найти гарантированно лучший ответ в таких задачах, нам нужно проверить все возможные комбинации. Но полный перебор занимает экспоненциальное время. Динамическое программирование (DP) — это элегантный выход из этой ловушки. По сути, это полный перебор, наделенный памятью.

Анатомия DP: Состояния и Переходы

Любая задача на динамическое программирование базируется на двух свойствах:

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

Чтобы переложить задачу на язык DP, нужно определить две вещи:

Состояние (State) — набор параметров, однозначно описывающих текущую подзадачу (например, «на какой ступеньке мы стоим» или «сколько сдачи осталось выдать»).
Переход (Transition) — математическая формула или логическое правило, связывающее текущее состояние с предыдущими.

Рассмотрим это на классической задаче Climbing Stairs (LeetCode 70). Перед вами лестница из $N$ ступеней. За один шаг можно подняться на 1 или 2 ступени. Сколько существует способов добраться до вершины?

Если мы находимся на ступени $N$ , мы могли попасть туда только двумя путями: шагнув со ступени $N-1$ или со ступени $N-2$ . Значит, общее количество путей на ступень $N$ равно сумме путей для этих двух предыдущих ступеней.

Математически наш переход выглядит так: $F(N) = F(N-1) + F(N-2)$ Где $F(N)$ — это количество способов, $N$ — состояние, а сложение двух предыдущих значений — переход.

Ловушка наивной рекурсии

Если мы просто перенесем формулу $F(N) = F(N-1) + F(N-2)$ в код с помощью рекурсии, алгоритм будет работать бесконечно долго даже для небольших чисел.

Посмотрите на дерево вызовов. Чтобы вычислить ответ для 5-й ступени, алгоритм вызывает функцию для 4-й и 3-й. Но вызов для 4-й ступени снова вычисляет 3-ю. Ветка для 3-й ступени вычисляется дважды, для 2-й — трижды. Количество вызовов растет как $O(2^N)$ . Мы делаем огромную лишнюю работу.

Подход 1: Мемоизация (Top-Down)

Первый способ решить проблему — Мемоизация (от слова memo — памятка). Это подход «сверху вниз» (Top-Down). Мы оставляем рекурсию, но добавляем к ней кэш (обычно хеш-таблицу или массив).

Логика работы:

Перед тем как вычислять $F(N)$ , проверяем: нет ли уже ответа в кэше?
Если есть — немедленно возвращаем его за $O(1)$ .
Если нет — делаем рекурсивные вызовы, вычисляем ответ, записываем его в кэш и только потом возвращаем.

def climbStairs(n: int, memo: dict) -> int:
    if n in memo:
        return memo[n]
    if n <= 2:
        return n

    # Вычисляем и сразу сохраняем в кэш
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
    return memo[n]

Теперь каждая подзадача вычисляется ровно один раз. Временная сложность падает с $O(2^N)$ до $O(N)$ .

Подход 2: Табуляция (Bottom-Up)

Мемоизация прекрасна, но у нее есть недостаток — накладные расходы на вызовы функций. При больших $N$ мы рискуем получить переполнение стека вызовов (StackOverflow).

Второй подход — Табуляция (от слова table — таблица). Это подход «снизу вверх» (Bottom-Up). Мы избавляемся от рекурсии полностью. Вместо того чтобы начинать с $N$ и спускаться к базовым случаям, мы начинаем с базовых случаев и итеративно заполняем массив (таблицу) до $N$ .

Мы знаем, что $dp[1] = 1$ и $dp[2] = 2$ . Запустим цикл от 3 до $N$ , где каждая ячейка вычисляется на основе уже заполненных предыдущих.

def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Временная сложность остается $O(N)$ , но скрытая константа времени выполнения значительно меньше: простой цикл for работает быстрее, чем сотни рекурсивных вызовов.

Что выбрать на собеседовании?

Оба подхода имеют право на жизнь и ожидаются интервьюерами. Выбор зависит от конкретной задачи.

Характеристика	Мемоизация (Top-Down)	Табуляция (Bottom-Up)
Направление мысли	От сложной задачи к простым	От простых баз к сложной задаче
Реализация	Рекурсия + Hash Map / Массив	Цикл `for` + Массив / Матрица
Посещение состояний	Вычисляет только нужные состояния	Вычисляет все состояния подряд
Накладные расходы	Высокие (стек вызовов)	Минимальные (быстрый цикл)
Риск StackOverflow	Есть (при глубокой рекурсии)	Нет

Главный критерий выбора — плотность пространства состояний. Если для ответа на задачу $F(N)$ вам обязательно нужно вычислить абсолютно все предыдущие значения (как в лестнице), табуляция выиграет за счет скорости цикла.

Динамическое программирование — это не магия, а систематизация перебора. В следующих главах мы применим эту концепцию к более сложным структурам: двумерным массивам в задаче о рюкзаке и строкам, а также научимся сжимать память в табуляции с $O(N)$ до $O(1)$ , сохраняя только то, что действительно нужно для перехода.

Задача о рюкзаке (0/1 Knapsack) и её вариации

Представьте, что вы собираетесь в поход. Вместимость вашего рюкзака строго ограничена — 4 кг. Перед вами лежат три предмета: палатка (вес 4 кг, ценность 30), спальник (вес 3 кг, ценность 20) и котелок (вес 1 кг, ценность 15). Жадный алгоритм, выбирающий предметы с максимальной удельной ценностью, потерпит здесь фиаско. Он возьмет палатку (ценность 30, рюкзак полон). Но оптимальное решение — взять спальник и котелок: их суммарный вес равен 4 кг, а суммарная ценность — 35.

Когда жадный выбор не работает, а перебор всех комбинаций дает экспоненциальную сложность $O(2^N)$ , на сцену выходит двумерное динамическое программирование.

Почему одномерного состояния недостаточно

В базовых задачах динамического программирования состояние описывается одним параметром. Например, при подъеме по лестнице нам важно знать только номер текущей ступеньки.

В задаче о рюкзаке у нас два независимых ограничения, которые меняются в процессе принятия решений:

Какие предметы нам еще доступны для выбора?
Сколько свободного места осталось в рюкзаке?

Следовательно, состояние должно быть двумерным. Обозначим его как $dp[i][c]$ , где $i$ — индекс предмета, который мы сейчас рассматриваем, а $c$ — текущая доступная вместимость (capacity). Значение в этой ячейке будет хранить максимальную ценность, которую можно получить, выбирая из первых $i$ предметов при вместимости $c$ .

Формула перехода: брать или не брать (0/1)

Приставка «0/1» в названии паттерна означает, что каждый предмет уникален: мы можем либо проигнорировать его (0), либо взять ровно один раз (1). Дробить предметы нельзя.

Находясь в состоянии $dp[i][c]$ , мы смотрим на предмет с весом $w_i$ и ценностью $v_i$ . У нас есть два пути:

Пропустить предмет (0). Мы не берем текущий предмет. Вместимость рюкзака не меняется, ценность не добавляется. Мы просто наследуем лучший результат, который был достигнут для предыдущих предметов при той же вместимости: $dp[i-1][c]$ .
Взять предмет (1). Этот вариант доступен, только если предмет физически влезает в рюкзак, то есть $w_i \leq c$ . Если мы его берем, наша итоговая ценность увеличивается на $v_i$ . Но чтобы его положить, мы должны были оставить для него место. Значит, к ценности предмета мы прибавляем лучший результат для предыдущих предметов при вместимости, уменьшенной на вес текущего: $v_i + dp[i-1][c - w_i]$ .

Оптимальное решение — это максимум из этих двух вариантов.

Общая формула перехода:

dp[i][c] = \max(dp[i-1][c], v_i + dp[i-1][c - w_i])

Табуляция: заполнение 2D-массива

Чтобы решить задачу методом Bottom-Up (табуляция), мы создаем матрицу размером $(N + 1) \times (C + 1)$ , где $N$ — количество предметов, а $C$ — максимальная вместимость рюкзака.

Дополнительная нулевая строка и нулевой столбец служат базовыми случаями (Base Cases):

Если у нас 0 предметов ( $i = 0$ ), максимальная ценность равна 0 при любой вместимости.
Если вместимость равна 0 ( $c = 0$ ), мы не можем взять ни один предмет, ценность равна 0.

Далее мы проходим по матрице двумя вложенными циклами: внешний по предметам от 1 до $N$ , внутренний по вместимости от 1 до $C$ .

Сложность такого алгоритма составляет $O(N \times C)$ как по времени, так и по памяти. Это псевдополиномиальная сложность: она зависит не только от количества элементов на входе, но и от числового значения вместимости.

Вариации паттерна на LeetCode

В реальных задачах на собеседованиях вас редко попросят «написать алгоритм для рюкзака». Паттерн будет скрыт за бизнес-логикой. Главный навык — распознать 0/1 Knapsack по двум признакам:

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

Subset Sum (Сумма подмножества)

Классическая задача Partition Equal Subset Sum (LeetCode 416). Дан массив чисел, например [1, 5, 11, 5]. Нужно определить, можно ли разбить его на две части с одинаковой суммой.

Если сумма всех элементов нечетная — разбить нельзя. Если четная (здесь 22), то задача сводится к поиску подмножества, сумма которого равна ровно половине (11).

Это чистый 0/1 Knapsack, где «вес» элемента равен его «ценности», а вместимость рюкзака — это половина общей суммы. Разница лишь в том, что в ячейках $dp[i][c]$ мы храним не максимальную ценность, а булево значение: True (можно собрать сумму $c$ ) или False (нельзя).

Формула перехода меняется с поиска максимума на логическое ИЛИ:

dp[i][c] = dp[i-1][c] \lor dp[i-1][c - w_i]

Мы можем собрать сумму $c$ , если мы могли собрать её без текущего элемента, ИЛИ если мы могли собрать сумму $c - w_i$ , к которой текущий элемент добавит недостающий вес.

Target Sum

В задаче Target Sum (LeetCode 494) перед каждым числом в массиве нужно поставить знак + или -, чтобы получить заданную цель. Математически это сводится к разделению массива на два подмножества (положительные и отрицательные числа), что снова возвращает нас к логике Subset Sum и двумерному массиву состояний.

Двумерная матрица дает наглядность и гарантирует правильный порядок вычислений. Однако хранить всю матрицу $(N+1) \times (C+1)$ часто бывает избыточно — для вычисления текущей строки нам нужна только предыдущая. Это открывает путь к радикальной экономии памяти.

Паттерн Longest Common Subsequence и работа со строками в ДП

Как алгоритм git diff понимает, какие строки вы добавили, а какие удалили? Как биологи вычисляют процент сходства двух цепочек ДНК, если в процессе эволюции часть нуклеотидов выпала, а часть мутировала? В основе этих сложнейших систем лежит один из самых элегантных паттернов динамического программирования — поиск наибольшей общей подпоследовательности (Longest Common Subsequence, или LCS).

В задаче о рюкзаке (0/1 Knapsack) мы ввели двумерное состояние dp[i][c], потому что у нас было два независимых ограничения: количество рассмотренных предметов и оставшаяся вместимость. При работе с двумя строками логика остается той же: у нас есть строка $A$ и строка $B$ . Чтобы сравнить их, нам нужно отслеживать прогресс по каждой из них независимо. Это означает, что состояние снова будет двумерным: dp[i][j] будет хранить результат для префикса первой строки длины $i$ и префикса второй строки длины $j$ .

Подстрока против Подпоследовательности

Прежде чем строить матрицу, зафиксируем критически важное отличие, на котором сыплются многие кандидаты.

Подстрока (Substring) — это непрерывный участок строки. Для "abcde" подстроками будут "abc", "bcd", "cde".

Подпоследовательность (Subsequence) — это набор символов, сохраняющий относительный порядок, но допускающий пропуски. Для "abcde" подпоследовательностями будут "ace", "abd", "be".

Паттерн LCS ищет именно подпоследовательность. Если мы ищем LCS для строк "abcde" и "ace", ответом будет "ace" (длина 3).

Механика переходов в LCS

Определим состояние. Пусть dp[i][j] — это длина наибольшей общей подпоследовательности для первых $i$ символов строки $A$ и первых $j$ символов строки $B$ .

Базовый случай очевиден: если одна из строк пустая (длина 0), то общих символов быть не может. Значит, нулевая строка и нулевой столбец нашей матрицы будут заполнены нулями.

Теперь представим, что мы смотрим на последние символы текущих префиксов: $A[i-1]$ и $B[j-1]$ . У нас есть ровно два сценария.

Сценарий 1: Символы совпадают ( $A[i-1] = B[j-1]$ ) Отличные новости! Мы нашли общий символ. Он гарантированно удлиняет ту общую подпоследовательность, которую мы нашли для строк до этих символов. Формула перехода: $dp[i][j] = dp[i-1][j-1] + 1$ . Мы берем результат по диагонали (без учета текущих символов) и добавляем 1.

Сценарий 2: Символы различаются ( $A[i-1] \neq B[j-1]$ ) Текущие символы не могут быть частью общей подпоследовательности одновременно. Нам нужно чем-то пожертвовать. Мы можем либо игнорировать символ из строки $A$ , либо символ из строки $B$ . Поскольку нам нужна наибольшая длина, мы выбираем максимум из этих двух вариантов. Формула перехода: $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$ . Мы смотрим на ячейку сверху (отбросили символ $A$ ) и на ячейку слева (отбросили символ $B$ ) и берем максимум.

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

Паттерн 1: Longest Palindromic Subsequence

Мощь паттерна LCS в том, что он работает как скрытый движок для целого класса задач. Классический пример — задача Longest Palindromic Subsequence (LeetCode 516).

Дана строка, например, "bbbab". Нужно найти самую длинную подпоследовательность, которая читается одинаково слева направо и справа налево. В данном случае это "bbbb" (длина 4).

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

Достаточно создать перевернутую копию исходной строки (назовем ее rev) и найти LCS между оригиналом и rev. LCS("bbbab", "babbb") автоматически найдет самую длинную последовательность символов, которая присутствует в строке как в прямом, так и в обратном порядке — то есть палиндром!

Паттерн 2: Edit Distance (Расстояние Левенштейна)

Еще одна жемчужина строкового ДП — задача Edit Distance (LeetCode 72). Даны две строки, например, "horse" и "ros". Разрешены три операции: вставить символ, удалить символ, заменить символ. Нужно найти минимальное количество операций, чтобы превратить первую строку во вторую.

Состояние остается прежним: dp[i][j] — минимальное количество операций для префиксов длины $i$ и $j$ . А вот логика переходов меняется, отражая наши три доступные операции.

Если символы совпадают ( $A[i-1] = B[j-1]$ ), нам не нужно ничего делать. Стоимость 0. $dp[i][j] = dp[i-1][j-1]$

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

Замена (Replace): мы меняем $A[i-1]$ на $B[j-1]$ . Теперь они совпадают, и мы переходим к префиксам без этих символов. Это шаг по диагонали: $dp[i-1][j-1]$ .
Удаление (Delete): мы удаляем $A[i-1]$ и надеемся, что оставшаяся часть $A$ совпадет с текущим префиксом $B$ . Это шаг вверх: $dp[i-1][j]$ .
Вставка (Insert): мы искусственно вставляем нужный символ $B[j-1]$ в конец $A$ . Теперь этот символ совпал, и нам нужно собрать оставшуюся часть $B$ из текущего префикса $A$ . Это шаг влево: $dp[i][j-1]$ .

Итоговая формула при несовпадении: $dp[i][j] = 1 + \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])$

Геометрия матрицы идеально отражает эти операции. Движение по таблице — это не просто абстрактные индексы, это конкретные действия над текстом.

Оба алгоритма — и классический LCS, и Edit Distance — требуют заполнения двумерной матрицы. Это означает, что их временная сложность составляет $O(N \times M)$ , где $N$ и $M$ — длины строк. Пространственная сложность при наивной реализации также составляет $O(N \times M)$ . Однако, если внимательно посмотреть на формулы переходов, можно заметить одну особенность, которая позволит нам кардинально сократить потребление памяти.

Оптимизация памяти в ДП: Сжатие состояний до одномерного массива

В предыдущих главах мы научились решать классические задачи двумерного динамического программирования: 0/1 Knapsack, Longest Common Subsequence (LCS) и Edit Distance. Все они сводились к заполнению матрицы размером $N \times M$ .

Матрица отлично работает, когда длины строк или вместимость рюкзака измеряются тысячами. Но что произойдет, если на вход поступят две строки по $100 000$ символов? Матрица $10^5 \times 10^5$ потребует $10^{10}$ ячеек памяти. Если каждая ячейка — это 4-байтовое целое число, алгоритм попытается выделить около 40 гигабайт оперативной памяти и немедленно упадет с ошибкой Out of Memory.

На собеседованиях в BigTech работающее решение за $O(N \times M)$ по времени и памяти — это лишь первый этап. Интервьюер обязательно спросит: «Можем ли мы оптимизировать использование памяти до $O(M)$ ?».

Окно зависимости: Почему нам не нужна вся матрица

Ключ к оптимизации памяти кроется в формулах переходов (Transitions), которые мы вывели ранее. Посмотрим на базовый переход для задачи о рюкзаке:

$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w] + v)$

Чтобы вычислить любую ячейку в текущей строке $i$ , алгоритму нужны данные только из предыдущей строки $i-1$ . Строки $i-2$ , $i-3$ и более ранние больше никогда не будут прочитаны.

Это свойство называется окном зависимости (Dependency Window). В большинстве классических задач ДП на строках и массивах окно зависимости равно единице: текущий шаг зависит только от непосредственно предыдущего. Это означает, что хранить всю историю вычислений бессмысленно.

Уровень 1: Чередование двух строк

Самый простой и пуленепробиваемый способ сжать память — использовать два одномерных массива вместо матрицы: prev_row и curr_row.

Алгоритм выглядит так:

Инициализируем массив prev_row базовыми значениями (для $i=0$ ).
Для каждого следующего шага $i$ создаем пустой curr_row.
Заполняем curr_row, опираясь только на данные из prev_row.
После завершения внутреннего цикла делаем prev_row = curr_row (или меняем ссылки местами).

Этот подход снижает пространственную сложность с $O(N \times M)$ до $O(2 \times M)$ , что асимптотически равно $O(M)$ . Он работает всегда, если переход ссылается только на $i-1$ .

Но настоящая алгоритмическая элегантность заключается в том, чтобы обойтись ровно одним одномерным массивом.

Уровень 2: Один массив и магия направления обхода (0/1 Knapsack)

Попробуем сжать 0/1 Knapsack до одного массива $dp$ размером $C + 1$ (где $C$ — вместимость рюкзака). Мы хотим, чтобы массив $dp$ на шаге $i$ перезаписывал сам себя.

Формула с одним массивом выглядела бы так: $dp[j] = \max(dp[j], dp[j-w] + v)$

Здесь $dp[j]$ до присваивания играет роль $dp[i-1][j]$ (значение с прошлого шага), а после присваивания становится $dp[i][j]$ (новым значением).

Если мы будем заполнять массив слева направо (от $j=0$ до $C$ ), мы столкнемся с фатальной проблемой. Вычисляя $dp[j]$ , мы обращаемся к $dp[j-w]$ . Но поскольку мы идем слева направо, ячейка $dp[j-w]$ уже была обновлена на текущем шаге $i$ . Мы прибавим ценность предмета к состоянию, в котором этот же предмет уже мог быть взят. Это нарушает главное правило 0/1 Knapsack: каждый предмет можно взять только один раз.

Решение гениально в своей простоте: нужно обходить массив справа налево, от $C$ до $w$ .

При обходе справа налево, когда мы вычисляем $dp[j]$ и обращаемся к $dp[j-w]$ , ячейка слева от нас ( $j-w$ ) еще не была перезаписана на текущем шаге. В ней гарантированно лежат "чистые" данные с предыдущего шага $i-1$ .

Уровень 3: Проблема диагонали (LCS и Edit Distance)

Сжатие до одного массива в задачах на подстроки (LCS, Edit Distance) сталкивается с более сложной геометрией зависимостей.

Вспомним переход для Longest Common Subsequence при совпадении символов: $dp[i][j] = dp[i-1][j-1] + 1$

Нам нужны три значения для вычисления текущей ячейки:

Верхнее: $dp[i-1][j]$
Левое: $dp[i][j-1]$
Диагональное (верхнее-левое): $dp[i-1][j-1]$

Если мы используем один массив и идем слева направо:

Верхнее значение — это текущий $dp[j]$ (еще не перезаписан, берем смело).
Левое значение — это $dp[j-1]$ (уже перезаписан на текущем шаге, то что нужно).
Диагональное значение — это старый $dp[j-1]$ . Но мы его только что перезаписали на предыдущей итерации внутреннего цикла!

Если мы пойдем справа налево (как в рюкзаке), мы спасем диагональ, но потеряем левое значение, которое должно быть из текущего шага.

Трюк с переменной prev_diag

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

Алгоритм сжатия LCS до одномерного массива выглядит так:

Перед началом внутреннего цикла по $j$ сохраняем $dp[0]$ в переменную prev_diag.
Внутри цикла по $j$ $j$ :
- Сохраняем текущее значение $dp[j]$ во временную переменную temp (это верхнее значение, которое на следующей итерации станет диагональным).
- Вычисляем новое значение $dp[j]$ . Если символы совпали, используем prev_diag + 1. Если нет — берем $\max(dp[j], dp[j-1])$ .
- Обновляем prev_diag = temp.

Этот паттерн с одной дополнительной переменной позволяет сжать любую 2D матрицу с зависимостью от левого-верхнего соседа до $O(M)$ памяти.

Эвристика выбора метода сжатия

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

Всегда начинайте с 2D матрицы. Сначала убедитесь, что логика переходов работает корректно. Не пытайтесь писать 1D ДП с нуля, если задача сложная.
Если зависимость только от $i-1$ :
- Безопасный путь: используйте два массива (prev и curr). Это требует минимум умственных усилий и исключает баги перезаписи.
- Оптимальный путь: один массив. Если зависимость от левых элементов ( $j-w$ ) — обход справа налево. Если зависимость от правых элементов ( $j+w$ ) — обход слева направо.
Если зависимость от $i-1$ и $j-1$ одновременно (диагональ):
- Используйте один массив + переменную prev_diag.

Оптимизация памяти превращает просто "правильное" решение в решение уровня Senior. Вы показываете интервьюеру, что понимаете не только абстрактную математику переходов, но и то, как алгоритм физически ложится в архитектуру памяти компьютера.

Игры и теория принятия решений на LeetCode

До сих пор мы решали задачи, в которых противостояли «пассивной» среде. Мы упаковывали рюкзаки, искали общие подстроки и оптимизировали память, предполагая, что данные статичны. Но на собеседованиях часто встречается другой класс задач: у вас появляется оппонент.

В игровых задачах (Game Theory) вы больше не можете просто жадно забирать лучшие элементы или линейно обходить состояния. Ваш противник умен, рационален и активно пытается разрушить вашу стратегию. Чтобы победить, нужно научиться думать за двоих.

Анатомия идеальной игры

Задачи на LeetCode из этой категории обычно описывают игры с полной информацией (Perfect Information) и нулевой суммой (Zero-Sum Game).

Полная информация означает, что нет кубиков, скрытых карт или случайностей. Оба игрока видят все состояние игры.
Нулевая сумма означает, что выигрыш одного равен проигрышу другого. Если Алиса получает $+10$ очков, Боб теряет $10$ очков (или отстает на $10$ ).

Главное правило решения таких задач: всегда исходите из того, что оппонент играет оптимально. Никаких надежд на ошибку противника. Если у Боба есть хотя бы один ход, ведущий к его победе, он обязательно его найдет.

Ловушка математики: Nim Game

Прежде чем бросаться писать сложные матрицы динамического программирования, нужно проверить задачу на наличие математического паттерна. Часто игры на LeetCode — это замаскированные головоломки.

Классический пример — задача Nim Game (LeetCode 292). Перед вами куча из $N$ камней. Вы с оппонентом по очереди берете от 1 до 3 камней. Тот, кто забирает последний камень, побеждает. Вы ходите первым. При каком $N$ вы гарантированно выиграете?

Представим небольшие значения $N$ :

$N = 1, 2, 3$ : Вы просто забираете все камни. Победа.
$N = 4$ : Вы берете 1, 2 или 3 камня. Оппоненту остается 3, 2 или 1 камень соответственно. В свой ход он забирает остаток и побеждает. Поражение.
$N = 5, 6, 7$ : Вы можете взять столько камней, чтобы оставить оппоненту ровно 4. Как мы выяснили выше, тот, кто получает кучу из 4 камней, проигрывает. Победа.
$N = 8$ : Сколько бы вы ни взяли (1, 2, 3), вы оставите оппоненту 7, 6 или 5 камней. Из этих позиций он сможет оставить вам 4. Поражение.

Паттерн очевиден: если $N$ кратно 4, вы проигрываете при любой стратегии. В противном случае вы выигрываете. Решение занимает одну строку: return n % 4 != 0.

Как понять, что перед нами математический трюк, а не ДП? Смотрите на ограничения (Constraints). Если в задаче указано $N \leq 10^9$ , динамическое программирование создаст массив размером в миллиард элементов и упадет с ошибкой Memory Limit Exceeded или Time Limit Exceeded. Огромные ограничения — это кричащий сигнал: «Ищи формулу!».

Алгоритм Minimax: Когда математика бессильна

Если ограничения разумные (например, $N \leq 1000$ ), а правила сложнее банального взятия камней из одной кучи, в дело вступает алгоритм Minimax.

Суть Minimax в том, чтобы построить дерево всех возможных ходов. На своих ходах (уровни Max) игрок выбирает ветку с максимальным результатом. На ходах оппонента (уровни Min) предполагается, что оппонент выберет ветку с минимальным для первого игрока результатом.

Элегантность относительного счета

Рассмотрим задачу Predict the Winner (LeetCode 486). Дан массив чисел, например [1, 5, 233, 7]. Два игрока по очереди берут по одному числу либо с левого, либо с правого края массива. Побеждает тот, кто наберет большую сумму.

Если мы попытаемся хранить в состоянии ДП счет Алисы и счет Боба отдельно, наше состояние раздуется. Вместо этого используется гениальный трюк теории игр: относительный счет.

Относительный счет = (Мои очки) - (Очки оппонента).

Если в конце игры счет $> 0$ , я выиграл.
Если счет $< 0$ , выиграл оппонент.

Как это меняет логику переходов? Теперь нам не нужно знать, чей сейчас ход. Любой игрок в свой ход стремится максимизировать свой относительный счет.

Пусть dp(L, R) — это максимальный относительный счет, который может получить игрок, делающий ход прямо сейчас на подмассиве от индекса $L$ до $R$ .

У текущего игрока есть два варианта:

Взять левый элемент nums[L]. Тогда оппонент получит массив от $L+1$ до $R$ . Оппонент сыграет оптимально и заработает на этом остатке относительный счет dp(L+1, R). Значит, наш итоговый счет при этом выборе составит: nums[L] - dp(L+1, R).
Взять правый элемент nums[R]. Аналогично, оппонент заработает dp(L, R-1). Наш счет составит: nums[R] - dp(L, R-1).

Мы хотим максимизировать свой результат, поэтому формула перехода выглядит так:

dp(L, R) = \max(nums[L] - dp(L+1, R), nums[R] - dp(L, R-1))

Базовый случай и реализация

Базовый случай наступает, когда в массиве остается ровно один элемент ( $L = R$ ). Игрок просто забирает его, и его относительный счет увеличивается на значение этого элемента:

dp(L, R) = nums[L] \text{ при } L = R

Реализация через мемоизацию (Top-Down DP) выглядит невероятно лаконично:

def predictTheWinner(nums):
    memo = {}

    def dp(l, r):
        if l == r:
            return nums[l]
        if (l, r) in memo:
            return memo[(l, r)]

        pick_left = nums[l] - dp(l + 1, r)
        pick_right = nums[r] - dp(l, r - 1)

        memo[(l, r)] = max(pick_left, pick_right)
        return memo[(l, r)]

    # Алиса ходит первой. Если её итоговый относительный счет >= 0, она побеждает.
    return dp(0, len(nums) - 1) >= 0

Сложность такого решения — $O(N^2)$ по времени (так как у нас $N^2$ уникальных состояний (l, r)) и $O(N^2)$ по памяти для кэша.

Мы уже умеем сжимать состояния двумерного ДП до одномерного массива. Поскольку dp(L, R) зависит только от dp(L+1, R) (строка ниже) и dp(L, R-1) (ячейка слева), матрицу можно сжать до $O(N)$ памяти, обходя длины подмассивов от 1 до $N$ .

Резюме паттерна

Когда вы видите задачу на двух игроков, действуйте по алгоритму:

Проверьте ограничения. Если $N$ огромно — ищите математическую закономерность (четность, деление по модулю).
Определите состояние. Обычно это границы доступных данных (например, индексы $L$ и $R$ ).
Используйте относительный счет. Не храните очки обоих игроков. Считайте разницу: мой выбор - лучший ответ оппонента на остатке.
Примените ДП. Мемоизируйте результаты, так как игровые деревья содержат огромное количество перекрывающихся подзадач.

Игры с полной информацией конечны и детерминированы. Поняв принцип относительного счета, вы превращаете пугающего непредсказуемого оппонента в простую математическую формулу вычитания.

Бэктрекинг: Генерация перестановок и подмножеств

В прошлой главе мы разбирали алгоритм Minimax и научились находить оптимальный счет в игре. Но что, если интервьюер усложнит задачу: «Отлично, вы нашли максимальный выигрыш. А теперь выведите всю последовательность ходов, которая к нему приводит»? Или попросит сгенерировать все возможные валидные IP-адреса из строки цифр.

Динамическое программирование дает нам ответ на вопрос «сколько?» или «какой максимум?». Но когда нужно ответить на вопрос «как именно?» и перечислить все возможные комбинации, мы обращаемся к Backtracking (поиску с возвратом).

Суть Backtracking: DFS с кнопкой «Отмена»

Backtracking — это систематический перебор всех возможных вариантов (Brute Force), организованный в виде обхода в глубину (DFS) по дереву состояний.

Его главное отличие от обычного DFS на графах заключается в том, что граф не задан заранее. Мы строим его на лету, принимая решения на каждом шаге. А когда мы упираемся в тупик или находим валидный ответ, мы делаем шаг назад, отменяя свое последнее решение, чтобы попробовать другой путь.

Этот процесс описывается универсальным шаблоном из трех шагов: Choose (Выбрать) $\rightarrow$ Explore (Исследовать) $\rightarrow$ Unchoose (Отменить выбор).

def backtrack(path, options):
    if is_goal(path):
        result.append(path.copy()) # Сохраняем копию найденного пути
        return

    for choice in options:
        if is_valid(choice):
            path.append(choice)    # 1. Choose (Делаем выбор)
            backtrack(path, ...)   # 2. Explore (Идем глубже)
            path.pop()             # 3. Unchoose (Откатываем выбор)

На собеседованиях в BigTech 90% задач на Backtracking сводятся к двум базовым паттернам: генерации подмножеств (Subsets) и генерации перестановок (Permutations). Разберем их механику.

Паттерн 1: Подмножества (Subsets)

Задача: дан массив уникальных чисел, например [1, 2, 3]. Нужно вернуть все возможные подмножества (LeetCode 78).

В задачах на подмножества порядок элементов не важен ([1, 2] — это то же самое, что [2, 1]), а длина ответа может быть любой — от пустого множества [] до полного массива [1, 2, 3].

Логика построения дерева состояний здесь бинарная. На каждом шаге мы смотрим на конкретный элемент исходного массива и принимаем ровно два решения:

Взять этот элемент в текущее подмножество.
Пропустить этот элемент.

def generate_subsets(nums):
    result = []

    def backtrack(index, current_path):
        # В подмножествах любой путь — это валидный ответ
        result.append(current_path.copy())

        # Перебираем только те элементы, которые идут ПОСЛЕ текущего
        for i in range(index, len(nums)):
            current_path.append(nums[i])   # Choose
            backtrack(i + 1, current_path) # Explore (передаем i+1)
            current_path.pop()             # Unchoose

    backtrack(0, [])
    return result

Ключевой момент здесь — передача i + 1 в рекурсивный вызов. Это гарантирует, что мы движемся только вперед и никогда не возьмем один и тот же элемент дважды, а также не создадим дубликаты вроде [1, 2] и [2, 1].

Паттерн 2: Перестановки (Permutations)

Задача: дан массив уникальных чисел [1, 2, 3]. Нужно вернуть все возможные перестановки (LeetCode 46).

Здесь правила меняются. Длина каждого ответа строго равна длине исходного массива. Порядок имеет значение: [1, 2, 3] и [1, 3, 2] — это разные перестановки.

Поскольку на любую позицию мы можем поставить любой элемент (если он еще не был использован), нам больше не подходит движение строго слева направо через index. Нам нужен механизм отслеживания уже взятых элементов.

def generate_permutations(nums):
    result = []
    used = [False] * len(nums) # Массив для отслеживания использованных элементов

    def backtrack(current_path):
        if len(current_path) == len(nums):
            result.append(current_path.copy())
            return

        for i in range(len(nums)):
            if used[i]:
                continue # Пропускаем то, что уже в пути

            used[i] = True
            current_path.append(nums[i])

            backtrack(current_path)

            # Откат состояния: убираем из пути и помечаем как неиспользованный
            current_path.pop()
            used[i] = False

    backtrack([])
    return result

Вместо массива used в Python часто используют проверку if nums[i] in current_path. Но это скрытая ловушка на собеседовании: поиск в массиве занимает $O(N)$ , что увеличивает общую сложность. Массив used (или хеш-множество) дает проверку за $O(1)$ .

Архитектура дерева состояний

Хотя оба алгоритма используют один и тот же шаблон, форма пространства, которое они исследуют, кардинально различается.

Subsets: Дерево всегда имеет фиксированную глубину $N$ . На каждом уровне узел имеет все меньше ветвей, так как мы рассматриваем только оставшиеся справа элементы. Общее количество узлов (и ответов) равно $2^N$ .
Permutations: Дерево также имеет глубину $N$ , но ветвление работает иначе. На первом уровне у нас $N$ вариантов выбора, на втором $N-1$ , на третьем $N-2$ . Это классический факториал. Общее количество листьев равно $N!$ .

Constraints как главный индикатор

Backtracking — это алгоритмы экспоненциальной и факториальной сложности. Они чудовищно медленные. И именно это делает их самыми легко узнаваемыми задачами на LeetCode.

Вам даже не нужно дочитывать условие задачи до конца. Если вы посмотрите в раздел Constraints (Ограничения) и увидите там подозрительно маленькие числа, это прямой сигнал к действию.

Если $N \le 15$ — перед вами $O(2^N)$ . Ожидается генерация подмножеств или перебор бинарных состояний.
Если $N \le 10$ — перед вами $O(N!)$ . Ожидается генерация перестановок.

Для сравнения: $10! \approx 3.6 \times 10^6$ операций, что легко проходит лимит времени в 1 секунду. Но уже $12! \approx 4.7 \times 10^8$ , что гарантированно приведет к Time Limit Exceeded (TLE).

В следующей главе мы подробно разберем, как именно ограничения по времени (Time Limits) и размер входных данных диктуют выбор алгоритма еще до того, как вы напишете первую строчку кода.

Ограничения по времени (Time Limits) как подсказка к сложности алгоритма

В предыдущей главе, разбирая генерацию перестановок и подмножеств, мы опирались на жесткие рамки: $N \le 15$ или $N \le 10$ . Это не случайные числа, придуманные авторами задач для удобства. На платформе LeetCode, как и на реальном техническом интервью, размер входных данных (Constraints) — это легальная шпаргалка. Она прямо говорит вам, какой алгоритм ожидается в качестве оптимального решения.

Прежде чем вчитываться в запутанное условие задачи, опытные кандидаты прокручивают страницу вниз, к блоку Constraints. Значение $N$ позволяет мгновенно отсечь 80% неподходящих алгоритмических паттернов.

Физика серверов и правило $10^8$

Почему вообще возникают ошибки Time Limit Exceeded (TLE)?

Современные серверы тестирующих систем (включая LeetCode и HackerRank) способны выполнять примерно от $10^8$ до $4 \cdot 10^8$ базовых операций в секунду (сложения, присваивания, простые ветвления). Стандартный лимит времени на выполнение алгоритма для языков вроде C++ или Java составляет 1–2 секунды. Для Python лимиты обычно чуть мягче, но интерпретатор работает медленнее, поэтому базовый ориентир остается тем же.

Правило $10^8$ Чтобы ваш код гарантированно прошел тесты по времени, общее количество элементарных операций в худшем случае (Worst-Case Scenario) не должно превышать $10^8$ .

Зная это правило, мы можем реверс-инжинирить ожидаемую асимптотическую сложность Big-O. Если в задаче дан массив размером $N = 10^5$ , алгоритм со сложностью $O(N^2)$ потребует $(10^5)^2 = 10^{10}$ операций. Это в сто раз превышает лимит $10^8$ — система неизбежно выдаст TLE. Значит, писать вложенные циклы бессмысленно, нужно искать решение за $O(N \log N)$ или $O(N)$ .

Декодируем Constraints: Таблица-шпаргалка

Каждый диапазон значений $N$ жестко привязан к определенным классам алгоритмов. Запомнив эту таблицу, вы сможете направлять ход своих мыслей на собеседовании в нужное русло.

Ограничение $N$	Максимальный Big-O	Ожидаемые алгоритмы и паттерны
$N \le 10 \dots 15$	$O(N!)$ , $O(2^N)$	Backtracking (перестановки, подмножества), полный перебор.
$N \le 20 \dots 25$	$O(2^N)$ , $O(N \cdot 2^N)$	Битовые маски (Bitmasks), Meet-in-the-Middle.
$N \le 100 \dots 500$	$O(N^3)$ , $O(N^4)$	Трехмерное динамическое программирование, алгоритм Флойда-Уоршелла (графы).
$N \le 10^3 \dots 3 \cdot 10^3$	$O(N^2)$	Двумерное ДП (LCS, Edit Distance), вложенные циклы, плотные графы.
$N \le 10^4 \dots 10^5$	$O(N \log N)$ , $O(N)$	Сортировка, Two Pointers, Sliding Window, Hash Maps, BFS/DFS, Стек.
$N \ge 10^9$	$O(\log N)$ , $O(1)$	Бинарный поиск (по ответу), математические формулы, теория чисел.

Рассмотрим ключевые водоразделы подробнее.

Зона перебора: $N \le 25$

Если вы видите крошечное $N$ , не пытайтесь изобрести хитрый жадный алгоритм или сложную математику. Вас прямо просят перебрать все варианты. Для $N = 10$ ожидается $O(N!)$ (генерация перестановок). Если $N = 20$ , факториал уже превысит лимит, но $2^{20} \approx 10^6$ отлично укладывается в $10^8$ , поэтому здесь царит генерация подмножеств или ДП по профилю.

Зона квадрата: $N \le 3000$

Это классическая территория $O(N^2)$ . Если задача на строки и длины обеих строк $M, N \le 1000$ , это почти стопроцентный маркер двумерного динамического программирования, где мы строим матрицу состояний. Если это массив, то допустим перебор всех пар элементов.

Зона линейности: $N = 10^5$

Самое популярное ограничение на LeetCode. $10^5$ — это кричащий сигнал: «Никаких вложенных циклов!». Здесь у вас два пути:

Выполнить сортировку за $O(N \log N)$ , а затем пройтись по массиву.
Использовать структуры данных вроде Hash Map или монотонного стека для решения за $O(N)$ .

Зона логарифма: $N \ge 10^9$

Когда $N$ достигает миллиарда, даже линейный проход $O(N)$ становится опасным и может не уложиться в 1 секунду (особенно в Python). Если вам нужно найти какое-то число в таком диапазоне, единственный выход — отсекать половину вариантов на каждом шаге. Это территория паттерна Binary Search on Answer или чисто математических формул за $O(1)$ .

Как применять это на реальном интервью FAANG

На платформе LeetCode ограничения всегда написаны внизу задачи. На реальном техническом собеседовании в BigTech интервьюер даст вам условие, в котором ограничений не будет.

Это не случайность, а часть проверки. Интервьюер ждет, что до написания первой строчки кода вы зададите уточняющие вопросы.

Представьте, вам дают задачу: «Дан массив чисел, найдите две суммы, которые равны target». Если вы сразу броситесь писать решение через Hash Map за $O(N)$ , интервьюер может сказать: «А что если массив отсортирован, но памяти у нас всего $O(1)$ ?».

Правильный алгоритм действий:

Выслушать задачу.
Спросить: «Каков ожидаемый размер массива $N$ ? Есть ли ограничения по памяти?».
Услышав ответ: « $N$ может достигать $10^5$ », вслух проговорить: «Поскольку $N = 10^5$ , алгоритм за $O(N^2)$ не подойдет по времени. Мне нужно целиться в $O(N \log N)$ или $O(N)$ ».

Такое рассуждение показывает системный инженерный подход. Вы не просто угадываете паттерн, а выводите его из физических ограничений системы.

Когда стандартные паттерны бессильны: Сила Brute Force

Вы изучили скользящее окно, два указателя, динамическое программирование и жадные алгоритмы. Ваш мозг натренирован искать структуру. На собеседовании вы видите задачу, пытаетесь натянуть на неё один из десятка известных паттернов — и ни один не подходит. Жадный выбор даёт ошибку, для ДП не хватает памяти, а сортировка разрушает исходные данные.

В этот момент многие кандидаты впадают в ступор. Им кажется, что они забыли какой-то секретный алгоритм. Но секрет в том, что иногда структура задачи намеренно отсутствует. И единственным верным подходом становится Brute Force (полный перебор) — но не наивный, а алгоритмически выверенный.

Иллюзия структуры: почему ломаются паттерны

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

Жадные алгоритмы требуют свойства жадного выбора (локальный оптимум всегда ведет к глобальному).
Динамическое программирование требует оптимальной подструктуры (решение большой задачи собирается из решений малых, а их количество ограничено).
Бинарный поиск требует монотонности пространства ответов.

Если этих свойств нет, применение паттерна приведет к неверному ответу. Главный навык Senior-разработчика — уметь доказать себе, что оптимизация невозможна.

Рассмотрим классический пример: поиск кратчайшего пути в графе. Если веса ребер положительные, мы используем алгоритм Дейкстры. Но что, если задача звучит так: «Найти самый длинный путь в графе без циклов, посетив каждую вершину ровно один раз»?

Вы не можете использовать жадный алгоритм (выбор самого длинного ребра сейчас может завести в тупик). Вы не можете использовать классическое ДП по вершинам, потому что состояние зависит не только от текущей вершины, но и от всего набора ранее посещенных вершин (иначе вы замкнете цикл). Оптимальная подструктура разрушена историей посещений. Это NP-полная задача (Задача коммивояжера), и её ожидаемое решение — полный перебор всех возможных путей.

Умный Brute Force: Фиксация параметра

Полный перебор не означает написание пяти вложенных циклов for. Профессиональный Brute Force — это искусство сокращения пространства поиска. Главный инструмент здесь — фиксация параметра (Anchor/Fixing technique).

Суть метода: если задача требует найти комбинацию из нескольких элементов, и их одновременный поиск дает недопустимую сложность (например, $O(N^3)$ ), мы искусственно «замораживаем» один из параметров. Относительно зафиксированного параметра задача часто сводится к уже известному паттерну меньшей размерности.

Представьте задачу: дан массив чисел, нужно найти три элемента, сумма которых равна целевому значению (3Sum). Наивный перебор всех троек — это $O(N^3)$ .

Вместо того чтобы двигать три указателя одновременно, мы фиксируем первый элемент. Как только первый элемент зафиксирован, задача превращается в поиск двух элементов в оставшейся части массива, сумма которых равна Target - A[i]. А это уже решается паттерном Two Pointers за $O(N)$ . Итоговая сложность падает до $O(N^2)$ .

Фиксировать можно не только крайние элементы, но и «центр» структуры. Например, при поиске всех палиндромов в строке перебор всех возможных подстрок и проверка каждой займет $O(N^3)$ . Но если зафиксировать центр потенциального палиндрома (один символ или промежуток между двумя) и расширяться влево и вправо, сложность падает до $O(N^2)$ . Мы перебираем $N$ центров, и для каждого делаем максимум $N/2$ шагов.

Meet in the Middle: Когда N слишком велико для перебора

В главе про оценку сложности мы вывели правило: если $N \le 20$ , ожидается алгоритм за $O(2^N)$ (например, генерация всех подмножеств через Backtracking).

Но что делать, если $N = 40$ ? Для ДП нет подходящего состояния, жадный подход не работает. Ограничение намекает на перебор, но $2^{40}$ — это больше триллиона операций, что гарантированно приведет к Time Limit Exceeded (TLE). Сервер LeetCode переваривает около $10^8$ операций в секунду.

Здесь на сцену выходит техника Meet in the Middle (Встреча посередине). Это мост между полным перебором и бинарным поиском.

Алгоритм работает так:

Исходный массив из $N$ элементов делится ровно пополам: на левую и правую части по $N/2$ элементов.
Для каждой половины запускается независимый полный перебор (Backtracking). Генерируются все возможные суммы/комбинации.
Поскольку размер половины равен 20, каждая генерация создаст $2^{20}$ вариантов (около 1 миллиона). Это легко помещается в память и укладывается во время.
Теперь у нас есть два массива результатов. Задача сводится к тому, чтобы найти комбинацию одного элемента из левого массива и одного из правого, которая удовлетворяет условию.
Мы сортируем правый массив результатов за $O(K \log K)$ , где $K = 2^{N/2}$ .
Проходим по левому массиву и для каждого значения ищем дополнение в правом массиве с помощью бинарного поиска.

Сложность падает с невозможных $O(2^N)$ до вполне реальных $O(2^{N/2} \cdot \log(2^{N/2}))$ , что математически упрощается до $O(N \cdot 2^{N/2})$ . Для $N=40$ это около $40 \times 10^6$ операций — идеальное попадание в лимиты.

Стратегия на интервью

В BigTech-собеседованиях (особенно в Meta и Google) Brute Force играет особую роль. Интервьюер часто дает задачу, ожидая услышать наивный перебор в первые 3 минуты общения.

Озвучивание Brute Force решения решает три задачи:

Калибровка понимания: вы доказываете, что правильно поняли условие и можете решить задачу хотя бы теоретически.
Определение Baseline: вы фиксируете худшую возможную сложность (например, $O(N^4)$ ). Любой ваш следующий шаг должен быть строго лучше этой оценки.
Поиск узких мест: когда вы описываете наивный перебор, становится очевидно, какая именно часть делает лишнюю работу. Именно к этой части вы затем применяете фиксацию параметра или хеш-таблицу.

Никогда не молчите, пытаясь сразу в уме родить оптимальный паттерн. Скажите: «Самый прямолинейный способ решить это — перебрать все возможные комбинации за $O(2^N)$ . Но учитывая, что $N = 10^5$ , это не сработает. Давайте посмотрим, можем ли мы зафиксировать один из параметров...». Это фраза, которую произносят Senior-инженеры.

Эволюция решения: От наивного перебора к мемоизации и битовым маскам

На реальном собеседовании в FAANG от вас редко ждут оптимального кода в первые пять минут. Интервью — это процесс. Вы получаете задачу с ограничением $N \leq 18$ . Вы понимаете, что полный перебор даст $O(N!)$ , что для 18 элементов составляет астрономические $6 \times 10^{15}$ операций. Сервер упадет с Time Limit Exceeded. Но именно с этого «плохого» решения начинается путь к офферу.

Сегодня мы пройдем классическую эволюцию: напишем наивный перебор, найдем в нем перекрывающиеся подзадачи, добавим мемоизацию и, наконец, сожмем память с помощью битовых масок, превратив $O(N!)$ в элегантные $O(N \cdot 2^N)$ .

В качестве полигона возьмем классическую задачу о назначениях: есть $N$ рабочих и $N$ задач. Задана матрица cost, где cost[i][j] — стоимость выполнения $j$ -й задачи $i$ -м рабочим. Нужно распределить задачи так, чтобы минимизировать общую стоимость. Каждый рабочий берет ровно одну задачу.

Шаг 1: Baseline (Наивный перебор)

Опираясь на паттерны Backtracking из предыдущих глав, мы можем построить дерево решений. На каждом шаге мы берем текущего рабочего и пытаемся назначить ему одну из еще не занятых задач.

Состояние нашей рекурсии описывается двумя параметрами:

Индекс текущего рабочего (от 0 до $N-1$ ).
Список доступных задач (например, массив булевых флагов available).

Алгоритм прост: рабочий 0 перебирает все $N$ задач. Для каждой выбранной задачи он помечает ее как занятую и вызывает рабочего 1. Рабочий 1 перебирает оставшиеся $N-1$ задач, и так далее.

Временная сложность такого подхода — $O(N!)$ . Мы генерируем все возможные перестановки назначений. Это наш Baseline. Он работает корректно, но безнадежно медленно.

Шаг 2: Поиск перекрывающихся подзадач

Чтобы применить динамическое программирование, нам нужно найти в этом дереве перекрывающиеся подзадачи (Overlapping Subproblems). Давайте проследим за двумя разными ветками рекурсии для $N = 4$ :

Ветка А: Рабочий 0 берет задачу 1. Рабочий 1 берет задачу 3.
Ветка Б: Рабочий 0 берет задачу 3. Рабочий 1 берет задачу 1.

В обоих случаях, когда управление переходит к рабочему 2, список свободных задач абсолютно идентичен: остались задачи 0 и 2.

Рабочему 2 совершенно неважно, кто именно из его предшественников выполнил задачи 1 и 3. Ему важно лишь то, какие задачи остались. Минимальная стоимость распределения оставшихся задач 0 и 2 между рабочими 2 и 3 будет одинаковой для обеих веток.

В наивном переборе мы вычисляем эту минимальную стоимость для рабочих 2 и 3 дважды. А при больших $N$ — миллионы раз. Дерево решений на самом деле является направленным ациклическим графом (DAG), где множество путей ведет в одни и те же узлы.

Шаг 3: Мемоизация и проблема памяти

Раз мы нашли перекрывающиеся подзадачи, решение очевидно — нужно кэшировать результаты (мемоизация).

Ключом для кэша должно стать наше состояние: (worker_index, available_tasks). Но здесь возникает инженерная проблема. Как использовать массив или Hash Set в качестве ключа хеш-таблицы?

Если мы используем строковое представление массива (например, "True,False,True"), то на каждом шаге рекурсии мы будем тратить $O(N)$ времени на генерацию этой строки и вычисление ее хеша. Кроме того, хранение сотен тысяч таких строк быстро исчерпает лимит памяти.

Нам нужен способ представить множество доступных задач так, чтобы оно занимало $O(1)$ памяти, копировалось за $O(1)$ времени и могло служить быстрым ключом для массива или хеш-таблицы.

Шаг 4: Битовые маски как идеальное множество

Здесь на сцену выходят ограничения задачи (Constraints). Если $N \leq 18$ , то количество задач не превышает количества бит в стандартном 32-битном целом числе (Integer).

Мы можем представить множество available_tasks в виде одного числа — битовой маски (Bitmask). Каждый бит числа соответствует одной задаче. Если $i$ -й бит равен 1, задача свободна. Если 0 — задача выполнена.

Например, для $N = 5$ начальное состояние, когда все задачи свободны, выглядит как 11111 в двоичной системе (что равно числу 31 в десятичной).

Чтобы работать с маской, нам нужны всего две операции, которые выполняются процессором за один такт:

1. Проверка: свободна ли задача $i$ ? Нам нужно узнать, равен ли $i$ -й бит единице. Для этого берем число 1, сдвигаем его влево на $i$ позиций (получаем число, где только $i$ -й бит равен 1) и применяем побитовое И (AND). Если mask & (1 << i) не равно 0, значит задача свободна.

2. Изменение: отметить задачу $i$ как выполненную. Нам нужно превратить $i$ -й бит из 1 в 0, не трогая остальные. Для этого мы можем использовать побитовое исключающее ИЛИ (XOR). Новая маска: next_mask = mask ^ (1 << i). (Примечание: XOR инвертирует бит. Поскольку мы точно знаем, что до этого шага бит был равен 1, XOR безопасно превратит его в 0).

Финальная оценка сложности

Заменив массив свободных задач на одно целое число, мы получаем идеальное состояние для динамического программирования. Наш кэш теперь — это просто двумерный массив dp[worker_index][mask].

Давайте посчитаем новую сложность.

Параметр worker_index принимает $N$ значений.
Параметр mask принимает $2^N$ значений (от 0 до $2^N - 1$ ).
Итого уникальных состояний: $N \times 2^N$ .
Внутри каждого состояния мы делаем цикл по $N$ задачам, чтобы найти свободную.

Итоговая временная сложность: $O(N \cdot 2^N)$ . Пространственная сложность (память для кэша): $O(N \cdot 2^N)$ .

Вернемся к нашему собеседованию и $N = 18$ . Наивный перебор требовал $18! \approx 6 \times 10^{15}$ операций. Решение с масками требует $18 \times 2^{18} \approx 18 \times 262144 \approx 4.7 \times 10^6$ операций.

Мы сократили время выполнения с нескольких лет до миллисекунд, уложившись в правило $10^8$ операций. При этом мы не придумывали сложный математический алгоритм — мы просто взяли полный перебор, заметили, что история выборов не важна, и сжали состояние множества до размера одного числа. Это и есть алгоритмическая зрелость.

Битовые манипуляции: Трюки с XOR и масками для экономии памяти

Представьте, что на собеседовании вам дают массив из 100 000 целых чисел. Все числа в нем встречаются ровно дважды, и только одно число — единожды. Ваша задача — найти это уникальное число.

Первая мысль: завести хеш-таблицу, подсчитать частоту каждого элемента и вернуть тот, у которого частота равна единице. Отличное решение за $O(N)$ по времени. Но интервьюер улыбается и добавляет ограничение: «А теперь сделайте это, используя $O(1)$ дополнительной памяти».

В прошлой главе мы выяснили, как битовые маски помогают компактно хранить состояния в динамическом программировании. Сегодня мы спустимся на уровень самих битовых операций. В BigTech алгоритмические задачи на битовые манипуляции (Bit Manipulation) почти всегда преследуют одну цель — экстремальную экономию памяти.

Магия XOR: Уничтожение пар

Операция «исключающее ИЛИ» (XOR, обозначается символом $\oplus$ или оператором ^ в коде) работает по простому правилу: возвращает 1, если биты различны, и 0, если биты одинаковы.

Из этого правила вытекают три фундаментальных математических свойства:

Любое число XOR само себя дает ноль: $A \oplus A = 0$ .
Любое число XOR ноль остается самим собой: $A \oplus 0 = A$ .
Коммутативность и ассоциативность: порядок операций не важен. $A \oplus B \oplus A = A \oplus A \oplus B = 0 \oplus B = B$ .

Именно эти свойства элегантно решают задачу поиска уникального числа (LeetCode 136: Single Number). Если мы применим XOR последовательно ко всем элементам массива, все парные числа «уничтожат» друг друга, превратившись в нули. Единственное число, оставшееся без пары, сделает XOR с итоговым нулем и останется самим собой.

Вам не нужно сортировать массив или выделять память под хеш-таблицу. Всего одна переменная-аккумулятор и один проход циклом дают решение за $O(N)$ по времени и $O(1)$ по памяти.

Разделение потоков: Поиск двух уникальных чисел

Усложним задачу. Теперь в массиве два уникальных числа, а все остальные встречаются по два раза (LeetCode 260: Single Number III). Ограничение по памяти остается $O(1)$ .

Если мы применим общий XOR ко всему массиву, пары снова уничтожатся, но в результате мы получим $A \oplus B$ (где $A$ и $B$ — искомые уникальные числа). Извлечь из их суммы $A$ или $B$ напрямую невозможно.

Однако мы знаем одну важную вещь: поскольку $A$ и $B$ — разные числа, в их двоичном представлении есть как минимум один бит, который у них отличается. В результате $A \oplus B$ этот бит будет равен 1.

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

Числа, у которых этот бит равен 1.
Числа, у которых этот бит равен 0.

Число $A$ попадет в одну группу, а число $B$ — в другую. Все парные дубликаты разойдутся по группам вместе (ведь у одинаковых чисел все биты одинаковы). Теперь достаточно применить базовый алгоритм Single Number (общий XOR) к каждой группе по отдельности!

Остается технический вопрос: как алгоритмически вытащить этот самый отличающийся бит (любой единичный бит из результата $A \oplus B$ )?

Трюк изоляции младшего бита: x & (-x)

Самый быстрый способ найти установленный бит — изолировать самую младшую единицу числа (Lowest Set Bit). Для этого в программировании существует классический паттерн: mask = x & (-x).

Чтобы понять, почему это работает, нужно вспомнить, как компьютеры хранят отрицательные числа. Используется дополнительный код (Two's complement). Чтобы получить -x, процессор инвертирует все биты числа x (получая ~x), а затем прибавляет единицу.

Прибавление единицы к инвертированному числу вызывает цепную реакцию переноса разрядов справа налево. Эта реакция останавливается ровно на том месте, где в исходном числе x стояла самая младшая единица.

В результате у чисел x и -x младший единичный бит совпадает, а все биты левее него — строго противоположны. Применение побитового И (&) обнуляет всё, кроме этого самого младшего бита.

Получив маску вида 001000, мы можем легко отфильтровать элементы массива по условию (num & mask) != 0, разделив их на две независимые группы для итогового XOR.

Алгоритм Брайана Кернигана: Быстрый подсчет битов

Еще один частый класс задач — анализ самих битов. Например, нужно посчитать количество единиц в двоичном представлении числа (LeetCode 191: Number of 1 Bits).

Наивный подход — сдвигать число вправо в цикле while (x != 0) и проверять младший бит через x & 1. Это работает, но требует ровно 32 итераций для 32-битного числа, даже если в нем всего одна единица (например, число $1073741824$ , где установлен только 30-й бит).

Для разреженных битовых масок (где единиц мало) идеально подходит алгоритм Брайана Кернигана. Его основа — операция x & (x - 1).

Что происходит при вычитании единицы из числа? Самый младший единичный бит превращается в 0, а все нули правее него превращаются в 1. Например, если $x = 12$ (в двоичном виде 1100), то $x - 1 = 11$ (1011).

Если теперь применить побитовое И между $x$ и $x - 1$ , то самая младшая единица гарантированно обнулится, а остальные единицы (которые левее) останутся нетронутыми: 1100 & 1011 = 1000.

Каждое выполнение x = x & (x - 1) «откусывает» ровно одну единицу справа. Цикл будет работать ровно $K$ раз, где $K$ — количество единиц в числе. Сложность становится $O(K)$ вместо $O(32)$ .

Битовые трюки — это не просто низкоуровневая оптимизация компилятора. На собеседованиях в FAANG это полноценный математический инструмент, который позволяет обходить фундаментальные ограничения структур данных, превращая $O(N)$ памяти в $O(1)$ . В следующей главе мы продолжим математическую тему и разберем подходы к задачам на теорию чисел и геометрию.

Математические задачи на LeetCode: Теория чисел и геометрия

Вы написали математически безупречное решение. Формулы верны, логика идеальна. Вы нажимаете Submit и получаете... Time Limit Exceeded. Или, что еще обиднее, Wrong Answer на 142-м тесте из-за погрешности округления 0.3333333333333333 != 0.3333333333333334.

Математика на алгоритмических секциях BigTech — это не проверка вашего умения брать интегралы. Это проверка того, как вы адаптируете чистую математику к суровым реалиям вычислительных систем: ограниченной памяти, дискретному времени и несовершенству типов данных с плавающей точкой.

Теория чисел: От наивного поиска к Решету Эратосфена

Классическая задача: найти количество простых чисел строго меньших $N$ (LeetCode 204: Count Primes).

Если перебирать каждое число и проверять его на простоту, деля на все числа до $\sqrt{k}$ , мы получим временную сложность $O(N \sqrt{N})$ . При $N = 5 \times 10^6$ (типичное ограничение) это потребует более $10^9$ операций, что гарантированно приведет к TLE.

Здесь на сцену выходит алгоритм, придуманный более двух тысяч лет назад — Решето Эратосфена (Sieve of Eratosthenes). Идея заключается не в том, чтобы проверять каждое число, а в том, чтобы, найдя простое число, сразу исключить все его кратные из дальнейшего рассмотрения.

Ключевая оптимизация алгоритма, которую часто забывают на собеседованиях: внутренний цикл вычеркивания кратных для простого числа $p$ нужно начинать не с $2p$ , а сразу с $p^2$ . Почему? Потому что все меньшие кратные ( $2p$ , $3p$ , $5p$ ) уже были вычеркнуты ранее, когда мы обрабатывали простые числа $2$ , $3$ и $5$ .

Сложность Решета Эратосфена составляет $O(N \log \log N)$ . Это настолько близко к $O(N)$ , что на практике алгоритм работает как линейный. Пространственная сложность — $O(N)$ для хранения булевого массива.

Алгоритм Евклида: Быстрый НОД без факторизации

Найти Наибольший Общий Делитель (GCD — Greatest Common Divisor) двух чисел — базовая подзадача во множестве алгоритмов. Наивный подход требует разложения чисел на простые множители, что крайне медленно.

Алгоритм Евклида опирается на элегантное свойство: НОД двух чисел не меняется, если большее число заменить на остаток от деления большего на меньшее.

GCD(a, b) = GCD(b, a \pmod b)

Базовый случай наступает, когда $b = 0$ . Тогда $a$ и есть искомый НОД.

Код на Python выглядит обманчиво просто:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Временная сложность этого алгоритма — $O(\log(\min(a, b)))$ . Это означает, что даже для чисел порядка $10^{18}$ алгоритм выполнит не более пары десятков итераций.

Имея быстрый GCD, мы бесплатно получаем Наименьшее Общее Кратное (LCM — Least Common Multiple). Оно вычисляется по формуле:

LCM(a, b) = \frac{a \times b}{GCD(a, b)}

Практический совет: Сначала делите, а потом умножайте: $a / GCD(a, b) \times b$ . Это предотвратит переполнение целочисленного типа в языках вроде Java или C++, где $a \times b$ может выйти за пределы 64 бит до того, как вы разделите результат.

Вычислительная геометрия: Ловушка плавающей точки

Перейдем к геометрии. Задача: даны координаты точек на плоскости, нужно определить, лежат ли три заданные точки $A(x_1, y_1)$ , $B(x_2, y_2)$ и $C(x_3, y_3)$ на одной прямой (коллинеарны).

Первый инстинкт — школьная формула углового коэффициента (slope). Прямая едина, если наклон отрезка $AB$ равен наклону отрезка $BC$ :

k_1 = \frac{y_2 - y_1}{x_2 - x_1}, k_2 = \frac{y_3 - y_2}{x_3 - x_2}

Если $k_1 = k_2$ , точки на одной прямой. Но в программировании этот подход катастрофичен по двум причинам:

Деление на ноль: Если точки лежат на вертикальной прямой, $x_2 - x_1 = 0$ . Программа упадет с ошибкой.
Потеря точности: Тип float не может точно представить бесконечные дроби. Сравнение двух float через == — это лотерея.

Паттерн решения: Избавьтесь от деления. Преобразуйте уравнение, умножив обе части на знаменатели. Мы переходим от дробей к векторному произведению (Cross Product).

(y_2 - y_1)(x_3 - x_2) = (y_3 - y_2)(x_2 - x_1)

Если это равенство выполняется, точки коллинеарны. Мы используем только умножение и вычитание целых чисел. Никаких делений на ноль, никакой потери точности.

Геометрический смысл векторного произведения в 2D — это ориентированная площадь параллелограмма, натянутого на два вектора. Если площадь равна нулю, векторы параллельны (или лежат на одной прямой).

Пересечение прямоугольников: Сведение 2D к 1D

Еще один частый класс задач — работа с прямоугольниками, стороны которых параллельны осям координат (LeetCode 223: Rectangle Area). Нужно найти площадь их пересечения.

Попытка анализировать взаимное расположение углов в 2D-пространстве приводит к десяткам if-else условий: один внутри другого, пересекаются крестом, касаются углами и так далее. Учесть все краевые случаи практически невозможно.

Секрет в том, чтобы декомпозировать 2D-задачу на две независимые 1D-задачи. Прямоугольник — это просто два независимых отрезка: один на оси X, другой на оси Y.

Два прямоугольника пересекаются тогда и только тогда, когда пересекаются их проекции на ось X И их проекции на ось Y.

Как элегантно найти пересечение двух одномерных отрезков $[A, B]$ и $[C, D]$ ? Левая граница пересечения — это максимум из левых границ: $\max(A, C)$ . Правая граница пересечения — это минимум из правых границ: $\min(B, D)$ .

Длина пересечения:

Overlap = \max(0, \min(B, D) - \max(A, C))

Мы используем $\max(0, ...)$ , чтобы отсечь случаи, когда отрезки не пересекаются (тогда правая граница окажется левее левой, и разность будет отрицательной).

Применив эту логику независимо к осям X и Y, мы получаем площадь пересечения в три строки кода без единого if:

overlap_x = max(0, min(rect1_x_right, rect2_x_right) - max(rect1_x_left, rect2_x_left))
overlap_y = max(0, min(rect1_y_top, rect2_y_top) - max(rect1_y_bottom, rect2_y_bottom))
intersection_area = overlap_x * overlap_y

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

Чтение между строк: Как выявить скрытые ограничения в условии задачи

Вы применяете идеальный паттерн, пишете код за десять минут, нажимаете Submit — и получаете Wrong Answer на 73-м тесте. Почему? Потому что в условии было написано: «Дан массив целых чисел», а вы мысленно прочитали: «Дан массив положительных уникальных целых чисел».

В главе про Time Limits мы научились реверс-инжинирить алгоритм по размеру входа $N$ . Но ограничения (Constraints) скрывают в себе гораздо больше. В BigTech-интервью условие задачи — это юридический контракт. То, что в нём не сказано, так же важно, как и то, что сказано.

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

1. Ловушка переполнения: Когда $O(N)$ работает, но падает

Самая частая ошибка новичков — игнорирование диапазона значений элементов. Вы смотрите на $N \le 10^5$ и понимаете, что нужен линейный алгоритм. Но посмотрите на значения самих элементов: $-10^9 \le A[i] \le 10^9$ .

Представьте задачу: найти максимальную сумму подмассива. Вы заводите переменную int current_sum = 0. Если массив состоит из $10^5$ элементов, каждый из которых равен $10^9$ , максимальная сумма составит $10^{14}$ .

Стандартный 32-битный знаковый int вмещает значения примерно до $2 \cdot 10^9$ . На третьем элементе ваша переменная переполнится, уйдет в отрицательные значения, и алгоритм выдаст бессмысленный результат.

Правило чтения: Если в задаче требуется складывать или умножать элементы, а их значения достигают $10^4$ и выше — немедленно используйте 64-битные типы данных (long в Java/C++, long long, или встроенную длинную арифметику Python).

2. Знак числа: Разрушитель монотонности

Слова «целые числа» (integers) вместо «натуральные числа» (positive integers) полностью меняют правила игры. Наличие отрицательных чисел или нулей разрушает базовые предпосылки многих паттернов.

Пример 1: Sliding Window Классическое скользящее окно ищет подмассив с суммой $S$ . Мы расширяем окно вправо, пока сумма меньше $S$ , и сужаем слева, когда она превышает $S$ . Это работает только потому, что добавление элемента гарантированно увеличивает сумму. Если в массиве есть отрицательные числа, добавление элемента может уменьшить сумму. Монотонность нарушена, Sliding Window применять нельзя — придется использовать префиксные суммы с Hash Map.

Пример 2: Динамическое программирование и умножение В задаче Maximum Product Subarray мы ищем подмассив с максимальным произведением. Если числа только положительные, мы просто умножаем их. Но одно отрицательное число превращает огромный максимум в огромный минимум.

Пример 3: Графы Если веса ребер могут быть отрицательными, алгоритм Дейкстры (который мы разбирали ранее) использовать нельзя — он предполагает, что добавление ребра к пути может только увеличить его стоимость. Придется использовать алгоритм Беллмана-Форда.

3. Графы, притворяющиеся чем-то другим

Иногда условие задачи описывает граф, но с математическими ограничениями, которые превращают его в совершенно другую структуру. Распознавание этих скрытых структур экономит часы отладки.

Скрытое дерево

Условие гласит: «Дано $N$ серверов и $N-1$ соединений между ними. Любой сервер может связаться с любым другим».

Здесь нет слова «дерево». Но связный неориентированный граф из $N$ вершин и ровно $N-1$ ребер математически гарантированно является деревом. Что это значит для вас?

В графе нет циклов. Вам не нужен массив visited при обходе (достаточно передавать parent в рекурсию DFS).
Между любыми двумя узлами существует ровно один простой путь.

Функциональный граф

Условие: «Каждый человек из группы в $N$ человек подписан ровно на одного другого человека».

Это ориентированный граф, где из каждой вершины исходит ровно одно ребро (исходящая степень равна 1). Такая структура называется функциональным графом. Её скрытые свойства:

Из любой стартовой вершины вы неизбежно попадете в цикл.
Граф выглядит как набор циклов, к которым могут примыкать деревья, направленные к циклу (похоже на лассо или солнце с лучами).
Идеально решается паттерном Fast and Slow Pointers (черепаха и заяц), так как путь гарантированно зацикливается.

4. Строки и скрытое $O(1)$ по памяти

Когда вы видите задачу на строки, ищите фразу: «Строка состоит только из строчных букв английского алфавита» (consists of lowercase English letters).

Это ограничение — подарок. Оно означает, что размер алфавита фиксирован и равен 26. Если вам нужно подсчитать частоту символов, не используйте Hash Map. Хеш-таблица имеет накладные расходы на вычисление хеша, разрешение коллизий и хранение объектов. Вместо этого используйте простой массив int[26].

Обращение к array[char - 'a'] работает в разы быстрее, а память $O(26)$ в Big-O нотации схлопывается до $O(1)$ . Пространственная сложность вашего алгоритма становится константной, даже если строка имеет длину $10^5$ .

Чек-лист: Допрос условия задачи

Перед тем как написать первую строчку кода на собеседовании, прогоните условие через этот фильтр (и обязательно проговорите свои мысли вслух — интервьюеры это ценят):

Параметр	Что искать в условии	На что влияет
Размер $N$	$N \le 10^5$ или $N \le 15$	Выбор Big-O (отсекаем $O(N^2)$ или понимаем, что нужен Backtracking).
Тип данных	Суммы, произведения, факториалы	Риск переполнения $\rightarrow$ нужен 64-битный тип.
Домен значений	Могут ли быть $< 0$ ? А нули?	Ломает Sliding Window, влияет на деление (ошибка деления на ноль).
Уникальность	Элементы уникальны (distinct)?	Если нет $\rightarrow$ нужно пропускать дубликаты (например, в 3Sum или Subsets).
Порядок	Массив отсортирован?	Если да $\rightarrow$ это маркер для Binary Search или Two Pointers.
Топология	$N$ вершин, $N-1$ ребер, связность	Граф является деревом $\rightarrow$ циклов нет.

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

Интерактивный разбор: Общение с интервьюером во время написания кода

Представьте кандидата, который получает задачу, молча смотрит в монитор 15 минут, а затем за 5 минут пишет идеальный код с оптимальной сложностью $O(N)$ . Как вы думаете, каков будет вердикт интервьюера в Google или Meta? В 90% случаев это отказ.

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

В прошлой главе мы научились находить скрытые ограничения в условии задачи. Теперь наша цель — превратить эти находки в инструмент управления интервью.

Фаза 1: Синхронизация (первые 5–10 минут)

Самая частая ошибка начинающих — бросаться писать код сразу после прочтения условия. Пока вы не получили явное подтверждение от интервьюера, любая строчка кода может увести вас не туда.

Правильный старт состоит из трех шагов, которые нужно проговорить вслух.

Шаг 1. Вербализация ограничений

Вы нашли скрытое ограничение? Озвучьте его. Это показывает вашу инженерную зрелость.

— Я вижу, что массив содержит только строчные английские буквы. Значит, размер алфавита ограничен 26 символами. Я могу использовать массив фиксированного размера вместо хеш-таблицы, чтобы свести затраты памяти к $O(1)$ . Верно ли я понимаю, что других символов не будет?

Шаг 2. Озвучивание Baseline (базового решения)

Никогда не скрывайте, что вы видите наивное решение (Brute Force). Озвучив его, вы сразу задаете нижнюю границу эффективности.

— Самое простое решение здесь — перебрать все пары через вложенный цикл. Это займет $O(N^2)$ времени. Но, учитывая, что $N \leq 10^5$ , такое решение не уложится в лимит времени. Нам нужно целиться в $O(N \log N)$ или $O(N)$ .

Шаг 3. Запрос «Зеленого света» (Green Light)

Прежде чем писать код оптимизированного решения, опишите его идею (паттерн, структуры данных) и явно спросите разрешения начать.

— Чтобы достичь $O(N)$ , я планирую использовать паттерн Sliding Window. Я заведу два указателя и буду расширять окно вправо, пока сумма меньше цели, и сужать слева, если сумма превышена. Звучит ли этот подход разумно, или вы хотели бы увидеть реализацию через префиксные суммы?

Если интервьюер говорит: «Да, звучит отлично, давайте напишем», — вы получили Green Light. Теперь, даже если вы допустите баг в коде, интервьюер знает, что ваша архитектурная задумка была верной, и будет помогать вам, а не валить.

Фаза 2: Написание кода (Think Out Loud)

Писать сложный алгоритм и одновременно связно говорить — тяжело. Мозг не может одинаково эффективно выполнять две когнитивно сложные задачи. Поэтому в BigTech используется техника Signposting (разметка пути).

Вам не нужно комментировать каждую строчку в духе «сейчас я объявляю переменную i и присваиваю ей ноль». Вместо этого объявляйте намерения перед написанием логического блока.

Как работает Signposting:

Вы говорите: «Сначала я проинициализирую хеш-таблицу для подсчета частоты элементов и заполню ее».
Вы замолкаете на 15–20 секунд и молча пишете этот блок кода.
Вы говорите: «Отлично, теперь я напишу основной цикл, который будет проходить по массиву и проверять условия...»
Снова пишете молча.

Такой подход сохраняет контакт с интервьюером, но дает вам островки тишины для концентрации.

Что делать, если вы застряли?

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

Превратите свой ступор в инженерное обсуждение. Озвучьте альтернативы, между которыми вы выбираете, и их недостатки:

— Я сейчас немного застрял. Я пытаюсь решить, как эффективно удалять элементы из середины окна. Если я использую массив, удаление займет $O(N)$ . Если двусвязный список — удаление будет за $O(1)$ , но я потеряю доступ по индексу. Мне кажется, здесь нужна структура вроде Deque, чтобы сохранять монотонность. Что вы думаете?

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

Фаза 3: Завершение и анализ

Когда вы написали последнюю скобку, не откидывайтесь на спинку кресла со словами «Я всё». В реальной работе написание кода — это лишь половина дела. Код нужно проверить и оценить.

Сразу же после завершения логики возьмите инициативу в свои руки:

Зафиксируйте сложность: «Алгоритм готов. Временная сложность составляет $O(N)$ , так как каждый элемент добавляется и удаляется из дека максимум один раз. Пространственная сложность $O(K)$ , где $K$ — размер окна, так как дек хранит не более $K$ элементов».
Предложите проверку: «Теперь я хочу протестировать этот код на паре примеров, чтобы убедиться, что нет ошибок на границах массива».

Именно здесь начинается этап ручного прогона кода (Dry Run) — важнейший навык, который спасает от глупых опечаток и ошибок на $N=0$ или $N=1$ . О том, как проводить Dry Run так, чтобы интервьюер был в восторге, мы подробно поговорим в следующей главе.

Тестирование кода на бумаге: Сухой прогон (Dry Run) граничных случаев

Вы закончили писать код на маркерной доске или в простом текстовом редакторе без кнопки «Run». Интервьюер кивает и произносит: «Выглядит неплохо. Давайте проверим, как это работает». На этом этапе срезается около трети кандидатов, которые блестяще придумали алгоритм и озвучили сложность. Они начинают просто читать свой код вслух, водя пальцем по строкам: «Здесь мы заходим в цикл, здесь прибавляем единицу...». Это не тестирование. Это пересказ синтаксиса.

В BigTech ожидают инженеров, способных доказать работоспособность кода до его попадания в компилятор. Этот процесс называется Dry Run (сухой прогон) — ручная симуляция выполнения программы с отслеживанием изменения состояния памяти.

Анатомия правильного Dry Run: Таблица состояний

Главная ошибка при ручном тестировании — попытка удержать значения переменных в голове. На третьей итерации цикла вы неизбежно забудете, чему равен указатель left, и сделаете неверный вывод.

Профессиональный Dry Run начинается с создания таблицы состояний (State Table). Вы выписываете все ключевые переменные вашего алгоритма в виде заголовков столбцов, а каждая строка таблицы становится снимком памяти (snapshot) на конкретной итерации.

Рассмотрим классический пример — бинарный поиск числа $5$ в массиве nums = [1, 3, 5, 7].

Когда вы заполняете такую таблицу на глазах у интервьюера, вы демонстрируете абсолютный контроль над логикой. Вы не предполагаете, что код работает, — вы это показываете. Более того, если в коде есть ошибка (например, вы написали $L = mid$ вместо $L = mid + 1$ ), таблица немедленно выявит бесконечный цикл: значения $L$ и $R$ перестанут сближаться.

Искусство выбора тестовых данных

Интервьюер часто предлагает вам самостоятельно выбрать входные данные для проверки. Худшее, что можно сделать, — взять огромный пример из описания задачи, где $N = 10$ . Вы потратите 15 минут на рутинное заполнение таблицы и не успеете обсудить оптимизации.

Идеальный тестовый пример для Dry Run должен быть минимально достаточным. Он должен состоять из 3–5 элементов, но при этом заставлять алгоритм пройти через все ключевые ветвления (if/else) вашего кода.

Тестовые случаи делятся на три категории, которые необходимо проверить.

1. Happy Path (Счастливый путь)

Это стандартный сценарий, при котором алгоритм делает то, ради чего создавался. Если задача — найти сумму подмассива, Happy Path — это массив из 4-5 случайных положительных чисел. Этот прогон вы делаете первым, чтобы убедиться, что основная логика (циклы, переходы состояний) работает корректно.

2. Edge Cases (Граничные случаи)

Именно здесь прячется 90% багов. Граничные случаи — это экстремальные значения входных данных, при которых алгоритм ведет себя нестандартно. После успешного Happy Path вы обязаны прогнать код через 2-3 граничных случая.

Типичные маркеры для проверки:

Пустой ввод: nums = [] или s = "". Не упадет ли код с IndexOutOfBoundsException на первой же строке nums[0]?
Минимальный размер: nums = [1]. Отработает ли логика, если цикл for (int i = 1; i < n; i++) вообще не запустится?
Отсутствие искомого результата: Что вернет функция поиска, если элемента нет в массиве?
Дубликаты: nums = [2, 2, 2, 2]. Не зациклится ли алгоритм Two Pointers, если элементы равны?
Отрицательные числа: Если задача связана с суммами, проверьте массив [-1, -2, -3].

3. Malicious/Invalid Input (Некорректный ввод)

В контексте LeetCode это требуется редко, так как ограничения (Constraints) обычно гарантируют валидность данных. Но на системном интервью полезно вслух спросить: «Нужно ли мне обрабатывать случай, когда передается null вместо массива?».

Охота на ошибку «Off-by-One»

Самый частый баг, который выявляет сухой прогон, — это ошибка на единицу (Off-by-One Error). Она возникает на границах структур данных.

Представьте, что вы написали код для проверки, является ли массив палиндромом, используя два указателя: int L = 0, R = nums.length; while (L < R) { ... }

Без Dry Run код выглядит логично. Но как только вы начнете заполнять таблицу состояний для массива [1, 2, 1], вы запишете стартовые значения: $L = 0$ , $R = 3$ . На первой же итерации вы попытаетесь обратиться к nums[3] и получите ошибку выхода за пределы массива, потому что последний индекс равен $2$ .

Сухой прогон заставляет вас физически подставить индекс $3$ в мысленный массив, что моментально включает тревогу. Вы тут же исправляете код на R = nums.length - 1 еще до того, как интервьюер успеет указать на ошибку. Способность находить и исправлять собственные баги в процессе Dry Run оценивается интервьюерами так же высоко, как и написание безошибочного кода с первой попытки.

Симуляция интервью: Разбор сложной задачи FAANG без готового паттерна

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

В BigTech это происходит намеренно. Интервьюерам не интересно, как хорошо вы вызубрили LeetCode. Им интересно, как вы мыслите, когда сталкиваетесь с неопределенностью.

В этой главе мы проведем симуляцию реального интервью. Мы возьмем задачу, которая требует гибридного подхода, и пройдем через все фазы: от чтения между строк до написания и тестирования кода, опираясь на навыки коммуникации (Signposting) и ручного тестирования (Dry Run), которые мы разобрали в предыдущих главах.

Фаза 1: Условие и локализация проблемы

Интервьюер предлагает задачу, похожую на Maximum Number of Events That Can Be Attended (LeetCode 1353):

Вам дан массив events, где events[i] = [startDay, endDay]. Каждое событие начинается в день startDay и заканчивается в день endDay. Вы можете посетить только одно событие в день. При этом вы можете посетить событие i в любой день d, если startDay \le d \le endDay. Найдите максимальное количество событий, которые можно посетить.

Ваши первые действия: не бросаться писать код. Вы применяете технику Signposting и начинаете рассуждать вслух.

Анализ условия: «Итак, у меня есть интервалы. Но в отличие от классических задач на слияние интервалов (Merge Intervals), мне не нужно находиться на событии всё время. Мне нужно потратить ровно один день внутри интервала, чтобы событие засчиталось».
Запрос ограничений: Вы спрашиваете интервьюера: «Какие ограничения на размер массива и значения дней?». Интервьюер отвечает: «Длина массива $N \le 10^5$ , дни от $1$ до $10^5$ ».

Срабатывает рефлекс из главы про Time Limits: $N = 10^5$ означает, что алгоритм должен работать за $O(N \log N)$ или $O(N)$ . Любое решение за $O(N^2)$ , включая классическое двумерное динамическое программирование, неминуемо получит Time Limit Exceeded (TLE).

Фаза 2: Поиск Baseline и провал стандартных паттернов

Вы озвучиваете базовое решение (Brute Force): «Самый наивный подход — это Backtracking. Для каждого дня мы перебираем все доступные события, пробуем посетить одно, переходим к следующему дню, а затем делаем откат (Unchoose). Это даст сложность порядка $O(N!)$ , что абсолютно неприемлемо».

Интервьюер кивает. Вы получили Green Light на поиск оптимизации. Начинаем перебирать паттерны:

Динамическое программирование? Состояние должно включать текущий день и маску посещенных событий. Маска для $10^5$ элементов невозможна. ДП отпадает.
Жадный алгоритм? Это похоже на задачу о расписании (Interval Scheduling). В классической задаче мы сортируем события по времени окончания. Попробуем?

Вы озвучиваете свои мысли: «Если я просто отсортирую события по времени окончания и буду брать первое попавшееся, я могу совершить ошибку. Например, есть событие А [1, 5] и событие Б [2, 2]. Если я в день 2 выберу событие А (потому что оно началось раньше), я навсегда упущу событие Б, которое можно было посетить только в день 2. Событие А можно было отложить на день 3».

Фаза 3: Конструирование гибридного решения

Вы нащупали логику: в каждый конкретный день нужно выбирать то событие, которое закончится раньше всего. Это свойство жадного выбора. Но как эффективно находить такое событие каждый день?

Давайте визуализируем архитектуру нашего будущего алгоритма. Нам нужно как-то подавать события по мере наступления дней, а затем из доступных выбирать самое «срочное».

Выстраиваем цепочку рассуждений вслух (Signposting):

Чтобы двигаться по времени линейно, отсортируем исходный массив events по дню начала (startDay). Это стоит $O(N \log N)$ .
Заведем переменную current_day.
Когда наступает current_day, некоторые события становятся «доступными». Нам нужна структура данных, куда мы будем складывать доступные события и которая умеет быстро отдавать событие с минимальным endDay.
Эта структура — Min-Heap (Очередь с приоритетом). Добавление и извлечение стоят $O(\log N)$ .

Фаза 4: Симуляция алгоритма и Green Light

Вы предлагаете интервьюеру итоговый алгоритм:

Сортируем события по startDay.
Итерируемся по дням (переменная day).
В начале дня добавляем в Min-Heap время окончания (endDay) всех событий, которые начались в этот день.
Удаляем из Min-Heap все события, которые уже закончились (endDay < day), так как мы их пропустили.
Если куча не пуста, извлекаем одно событие (самое срочное) — мы посетили его сегодня! Увеличиваем счетчик.

Сложность: Каждое событие добавляется в кучу один раз и извлекается один раз. Это $O(N \log N)$ времени. Память $O(N)$ для кучи. Это идеально вписывается в ограничения $N \le 10^5$ .

Интервьюер дает Green Light. Прежде чем писать код, давайте посмотрим, как это работает в динамике.

Фаза 5: Написание кода и Dry Run

Получив одобрение, вы пишете код. Обратите внимание, как логика разбита на четкие блоки:

import heapq

def maxEvents(events):
    # 1. Сортируем по дню начала
    events.sort(key=lambda x: x[0])

    total_events = len(events)
    min_heap = []
    max_count = 0
    event_idx = 0
    day = 1

    # Продолжаем, пока есть необработанные события ИЛИ события в куче
    while event_idx < total_events or min_heap:
        # Оптимизация: если куча пуста, прыгаем на день начала следующего события
        if not min_heap and event_idx < total_events:
            day = max(day, events[event_idx][0])

        # 2. Добавляем в кучу все события, начавшиеся сегодня или раньше
        while event_idx < total_events and events[event_idx][0] <= day:
            heapq.heappush(min_heap, events[event_idx][1]) # кладем endDay
            event_idx += 1

        # 3. Удаляем из кучи просроченные события
        while min_heap and min_heap[0] < day:
            heapq.heappop(min_heap)

        # 4. Посещаем одно событие с наименьшим endDay
        if min_heap:
            heapq.heappop(min_heap)
            max_count += 1

        day += 1 # Переходим к следующему дню

    return max_count

Обязательный шаг — Dry Run (Сухой прогон). Вы не ждете, пока интервьюер найдет ошибку, а сами инициируете проверку на граничном случае (Edge Case). Возьмем events = [[1,2], [2,3], [3,4]].

Вы строите State Table в комментариях:

day = 1: event_idx становится 1. В куче [2]. Просроченных нет. Посещаем событие (pop 2). max_count = 1.
day = 2: event_idx становится 2. В кучу летит [3]. Просроченных нет. Посещаем (pop 3). max_count = 2.
day = 3: event_idx становится 3. В кучу летит [4]. Просроченных нет. Посещаем (pop 4). max_count = 3.
day = 4: event_idx = 3 (конец массива), куча пуста. Цикл while завершается. Ответ 3. Алгоритм отработал корректно.

Главный инсайт

Сложные задачи FAANG редко решаются одним чистым паттерном. Секрет успеха — в декомпозиции. В этой задаче мы использовали Сортировку, чтобы упорядочить поток времени, Жадный подход для логики выбора («бери то, что сгорит первым») и Min-Heap как структуру данных, способную поддерживать этот жадный выбор в условиях постоянно меняющегося набора доступных опций.

Умение жонглировать этими компонентами, опираясь на анализ ограничений (Constraints) и постоянную коммуникацию с интервьюером, — это и есть уровень Senior-кандидата.

Чек-лист подготовки: Что повторить за 24 часа до собеседования

До технического интервью в BigTech осталось ровно 24 часа. Худшее, что вы можете сделать прямо сейчас, — открыть нерешенную задачу уровня Hard на LeetCode, застрять на ней, сломать уверенность в себе и пойти на собеседование с ощущением «я ничего не знаю».

Спортивные тренеры используют термин тейперинг (tapering) — резкое снижение нагрузок перед важными соревнованиями, чтобы организм успел восстановиться и выйти на пик формы. В алгоритмических интервью работает тот же принцип. За сутки до часа «Икс» вы не выучите новый сложный алгоритм, но можете блестяще систематизировать то, что уже знаете, и настроить свой разум на рабочий ритм.

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

1. Ментальная карта: От ограничений к паттерну

На собеседовании у вас не будет тегов задачи. Единственная объективная подсказка, которую вам даст интервьюер (или которую вы должны у него запросить), — это ограничения на размер входных данных ( $N$ ).

Вспомните правило $10^8$ операций. Окиньте мысленным взором матрицу соответствий, которую мы разбирали ранее:

Что нужно прокрутить в голове прямо сейчас:

Если $N \le 15$ : Это территория факториалов и экспонент. Мой мозг должен сразу переключиться на Backtracking (генерация перестановок/подмножеств) или ДП с битовыми масками.
Если $N \le 100$ : Скорее всего, это $O(N^3)$ . Ищем двумерное ДП с дополнительным циклом внутри, либо алгоритм Флойда-Уоршелла на графах.
Если $N \le 10^4$ : Это классическое $O(N^2)$ . Здесь живут вложенные циклы, базовое ДП (например, Longest Common Subsequence) и обход графов.
Если $N \le 10^5$ : Самый частый гость. $O(N^2)$ даст Time Limit Exceeded. Мне нужно $O(N \log N)$ или $O(N)$ . Я буду использовать Two Pointers, Sliding Window, Hash Map, Сортировку или Монотонный стек.
Если $N \ge 10^9$ : Линейный проход невозможен. Это либо Бинарный поиск (по ответу), либо математика за $O(1)$ .

2. Ревизия «опасных зон» в базовых шаблонах

Не нужно перечитывать свои решения сотен задач. Вместо этого вспомните тонкие места в классических паттернах — те самые строчки, где вы чаще всего допускали ошибки Off-by-One (ошибки на единицу) или ловили бесконечные циклы.

Пройдитесь по этому списку и убедитесь, что помните нюансы:

Бинарный поиск: Какое условие в цикле вы используете? Если while (L <= R), то сдвиги должны быть строго L = mid + 1 и R = mid - 1. Если забудете + 1, получите бесконечный цикл.
Breadth-First Search (BFS): В какой момент вы добавляете узел в множество visited? Правильный ответ: строго перед добавлением в очередь (или в момент добавления), но не после извлечения. Иначе в графе с циклами вы добавите один и тот же узел в очередь много раз, и память закончится.
Связные списки (Linked Lists): Если задача подразумевает удаление или изменение головы списка (Head), всегда создавайте Dummy Node. Возвращать в конце нужно будет dummy.next.
Sliding Window: Четко разделяйте две фазы внутри внешнего цикла. Первая — расширение окна (добавление элемента R). Вторая — внутренний цикл while, который сжимает окно (двигает L), пока нарушено условие задачи.
Двумерное ДП: Как инициализировать базовые случаи (нулевую строку и нулевой столбец)? Зависит ли текущая ячейка от левой-верхней по диагонали? Если да, и вы оптимизируете память до одномерного массива, вам понадобится переменная prev_diag.

3. Тайминг: Симуляция 45 минут

Техническое интервью в FAANG длится 45 минут. Ваша задача — не просто написать код, а провести интервьюера по своему ходу мыслей. Если вы потратите 35 минут на молчаливое написание идеального кода, вы можете не пройти: интервьюер не увидит, как вы рассуждаете и реагируете на требования.

Распределение времени (золотой стандарт):

Минуты 0–5 (Синхронизация): Вы слушаете задачу. Задаете уточняющие вопросы (граничные случаи, отрицательные числа, дубликаты). Формируете тестовый пример (Happy Path).
Минуты 5–15 (Проектирование): Вы озвучиваете базовое решение (Brute Force). Анализируете ограничения. Предлагаете оптимизированный подход. Получаете Green Light от интервьюера.
Минуты 15–30 (Кодинг): Вы пишете код. Используете технику Signposting (озвучиваете намерение, затем пишете блок логики).
Минуты 30–40 (Dry Run): Вы не нажимаете кнопку Run. Вы берете свой тестовый пример и вручную, строчка за строчкой, прогоняете его через написанный код, заполняя State Table (таблицу состояний).
Минуты 40–45 (Вопросы): Завершение секции, ваши вопросы компании.

Ошибка новичка — начать писать код на 3-й минуте. Ошибка перфекциониста — проектировать решение 25 минут, оставив на код всего 5. Держитесь золотой середины.

4. Стратегия поведения в кризисных ситуациях

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

Запомните главное правило: собеседование проверяет инженерное мышление, а не память компилятора.

Если вы забыли точное название метода — напишите псевдокод или выдуманное название, предупредив интервьюера: «Я не помню точный синтаксис сортировки по убыванию в этом языке, поэтому напишу sortDescending(arr). Главное, что это работает за $O(N \log N)$ ». В 99% случаев интервьюер кивнет и вы пойдете дальше.
Если вы зашли в тупик с алгоритмом — вернитесь к Brute Force. Лучше написать работающий код за $O(N^2)$ и обсудить его недостатки, чем сдать пустой экран, пытаясь родить гениальное решение за $O(N)$ .

Финальное напутствие

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

Завтрашнее интервью — это не экзамен, где вас хотят завалить. Это симуляция рабочего дня, где ваш будущий коллега хочет понять: каково это — решать с вами сложную проблему у одной маркерной доски?

Закройте LeetCode. Выспитесь. Завтра вы покажете всё, на что способны. Удачи!

Анализ сложности: Как Big-O определяет ваш оффер

Анализ сложности: Как Big-O определяет ваш оффер

Время — это не секунды, а операции

Основные классы сложности (Time Complexity)

Главные правила Big-O: Искусство отбрасывать лишнее

Пространственная сложность (Space Complexity)

Секретный чит-код LeetCode: Ограничения (Constraints)

Паттерн Two Pointers: Сжатие пространства поиска

Паттерн Two Pointers: Сжатие пространства поиска

Как работает сжатие пространства поиска

Классика: Two Sum II

Неочевидное применение: Container With Most Water

Как распознать паттерн на интервью

Паттерн Sliding Window: Оптимизация вложенных циклов

Паттерн Sliding Window: Оптимизация вложенных циклов

Проблема перекрывающихся вычислений (Фиксированное окно)

Динамическое окно: когда размер неизвестен

Парадокс вложенного цикла: почему это O(N)?

Как распознать паттерн на интервью

Практикум: Переход от O(N^2) к O(N) за один присест

Практикум: Переход от O(N^2) к O(N) за один присест

Анатомия O(N²): Почему алгоритм тормозит?

Кейс 1: Непрерывные подмассивы (Sliding Window)

Кейс 2: Фильтрация на месте (Read/Write Pointers)

Как выбрать правильный паттерн?

Хеш-таблицы: Поиск за O(1) и компромиссы по памяти

Хеш-таблицы: Поиск за O(1) и компромиссы по памяти

Как купить время за память

Внутреннее устройство: откуда берется O(1)?

Проблема коллизий

Hash Set против Hash Map

Кульминация: Hash Set внутри Sliding Window

Резюме

Паттерн Fast and Slow Pointers: Поиск циклов без лишней памяти

Паттерн Fast and Slow Pointers: Поиск циклов без лишней памяти

Проблема зацикливания

Алгоритм Флойда: Заяц и Черепаха

Почему они гарантированно встретятся?

Поиск начала цикла (Фаза 2)

Массив как связный список: Выход за рамки

Резюме

Паттерн Merge Intervals: Работа с интервалами и перекрытиями

Паттерн Merge Intervals: Работа с интервалами и перекрытиями

Анатомия перекрытия

Базовый алгоритм слияния (LeetCode 56)

Оптимизация: Вставка без полной сортировки (LeetCode 57)

Анализ сложности

Стек и Дек: Монотонный стек для поиска ближайших элементов

Стек и Дек: Монотонный стек для поиска ближайших элементов

Концепция Монотонного стека

Механика на примере Daily Temperatures

Шаблон кода

Дек: Когда стека недостаточно

Очереди и Heap: Топ-K элементов и слияние списков

Очереди и Heap: Топ-K элементов и слияние списков

Анатомия Кучи (Heap)

Паттерн Top-K: Поиск K наибольших элементов

Паттерн K-way Merge: Слияние нескольких списков

Динамические перекрытия: Meeting Rooms II

Оценка памяти: In-place алгоритмы против выделения новых структур

Оценка памяти: In-place алгоритмы против выделения новых структур

Скрытая цена O(N)O(N)O(N) памяти

Массив как собственная хеш-таблица

Паттерн Sign-Flipping (Инверсия знака)

Кодирование двух значений в одном (Modulo Arithmetic)

Стратегия на интервью

Бинарные деревья: Глубокое погружение в DFS и BFS

Бинарные деревья: Глубокое погружение в DFS и BFS

Анатомия бинарного дерева

Обход в глубину: Depth-First Search (DFS)

Обход в ширину: Breadth-First Search (BFS)

DFS против BFS: Как выбрать?

Паттерн Tree Breadth-First Search: Поуровневый обход

Паттерн Tree Breadth-First Search: Поуровневый обход

Механика паттерна: «Заморозка» размера очереди

Практическое применение: Binary Tree Right Side View

Вариация: Зигзагообразный обход

Оценка сложности

Паттерн Tree Depth-First Search: Рекурсивный спуск и возврат значений

Паттерн Tree Depth-First Search: Рекурсивный спуск и возврат значений

Скрытая цена $O(N)$ памяти