Алгоритмы и структуры данных для LeetCode (для фронтенд‑разработчика)

Как проходить LeetCode: подход, паттерны, Big‑O

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

Зачем вам LeetCode как фронтенд‑разработчику

LeetCode тренирует навыки, которые реально полезны в инженерной работе:

• Быстро разбираться в требованиях и ограничениях
• Выбирать структуру данных под задачу
• Писать код, который не падает на краевых случаях
• Оценивать, почему решение тормозит и как улучшить

Если ваша цель — собеседования, то важно ещё одно:

• На интервью проверяют не «угадай правильный ответ», а ход мыслей, ясность и контроль сложности

Полезные разделы на LeetCode:

• LeetCode
• Top Interview 150

Главная идея курса

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

• проходить задачу по понятному алгоритму
• распознавать популярные паттерны
• оценивать сложность по времени и памяти (Big‑O)

Как решать задачу: пошаговый процесс

Шаг 1. Переведите условие в контракт

Контракт — это чёткое описание того, что функция получает и что должна вернуть.

Спросите себя:

• Что является входом: массив, строка, дерево, матрица?
• Что является выходом: число, массив, булево значение?
• Разрешены ли отрицательные числа, пустой массив, повторяющиеся элементы?

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

Шаг 2. Используйте ограничения как подсказку

Ограничения (constraints) — это диапазоны входных данных. Они почти всегда подсказывают нужный класс решений.

Типичные ориентиры:

• $n \le 10^2$ часто допускает $O(n^2)$
• $n \le 10^5$ обычно требует $O(n)$ или $O(n \log n)$
• вход — отсортирован, поиск, минимум/максимум часто намекают на бинарный поиск

Здесь $n$ — размер входа (например, длина массива), $O(\cdot)$ — «порядок роста» времени работы. Мы подробно разберём это ниже.

Шаг 3. Сначала придумайте простое решение

Сделайте базовый вариант:

• пусть даже медленный, но понятный и корректный
• на нём вы закрепите логику, а потом оптимизируете

На интервью это особенно важно: лучше показать рабочее решение и затем улучшить, чем молчать в поисках «идеала».

Шаг 4. Найдите паттерн

Паттерн — это повторяющийся тип решения. Большинство задач LeetCode — комбинация 10–15 паттернов.

Признаки паттерна:

• условия типа «подмассив/подстрока» → часто скользящее окно
• «два элемента/пара/сумма/разность» → часто two pointers или hash map
• «кратчайший путь/минимальные шаги» → часто BFS
• «все варианты/перебор решений» → часто backtracking

Шаг 5. Согласуйте структуру данных с паттерном

Структуры данных — это «контейнеры» с разной стоимостью операций.

Самые частые в задачах для JS/TS:

• Array для последовательностей
• Map для «ключ → значение» и поиска за амортизированное $O(1)$
• Set для проверки «видели ли мы элемент»
• стек как Array с операциями push/pop
• очередь для BFS (в JS часто делают через массив с указателем head, чтобы не использовать дорогой shift())

Шаг 6. Проверьте крайние случаи до кода

Крайние случаи (edge cases) — это входы, на которых решения чаще всего ломаются:

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

Если вы выписали 3–5 крайних случаев и мысленно прогнали алгоритм — вы сэкономите много попыток.

Шаг 7. Оцените Big‑O до отправки

Перед тем как жать Submit, ответьте:

• Сколько раз мы проходим по данным?
• Используем ли сортировку?
• Сколько памяти дополнительно выделяем?

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

• по времени (time complexity)
• по памяти (space complexity)

Паттерны, которые дадут максимум результата

Ниже — базовые паттерны, которые покрывают большую часть задач уровня Easy/Medium.

Таблица: паттерн → как узнать → типичный инструмент

Паттерн	Как узнать по условию	Типичная структура данных
Hash map (частоты/индексы)	«найти пару», «первый уникальный», «сколько раз встречается»	Map
Two pointers	«массив отсортирован», «приблизиться к цели», «удалить дубликаты на месте»	два индекса
Скользящее окно	«подстрока/подмассив», «максимум/минимум на интервале», «ровно/не более K»	два индекса + Map/Set
Стек монотонный	«следующий больший/меньший», «температуры», «гистограмма»	стек (Array)
BFS	«минимум шагов», «уровни», «кратчайший путь в невзвешенном графе»	очередь
DFS	«обойти всё», «проверить связность», «компоненты»	рекурсия/стек
Бинарный поиск	«отсортировано», «минимальное подходящее», «найти границу»	индексы
Динамическое программирование	«оптимум», «количество способов», «выбор/не выбор», повторяющиеся подзадачи	массив/Map

Важно: паттерн — это не «готовый код», а форма мысли. Например, скользящее окно — это всегда два указателя, которые поддерживают «текущее окно», плюс структура для состояния окна.

Big‑O простыми словами

Big‑O — это способ описать, как растёт время работы и память при росте входа. Он помогает сравнивать подходы.

Что означают $O(1)$, $O(n)$, $O(n \log n)$

• $O(1)$ — время почти не зависит от размера входа (например, прочитать arr[i])
• $O(n)$ — один проход по массиву длины $n$
• $O(n^2)$ — два вложенных цикла по $n$
• $O(n \log n)$ — часто это сортировка или «делим пополам и работаем с частями»

Здесь:

• $n$ — размер входа (например, длина массива)
• $\log n$ — «сколько раз можно делить на 2, пока не станет 1» (пример: бинарный поиск)

Быстрые ориентиры для практики

Операция/подход	Обычно по времени	Комментарий
Один цикл по массиву	$O(n)$	частый «идеальный» вариант
Вложенный цикл по массиву	$O(n^2)$	часто не проходит при $n=10^5$
Сортировка	$O(n \log n)$	почти всегда так, независимо от языка
Map/Set поиск/вставка	амортизированно $O(1)$	в худшем случае может деградировать, но в задачах обычно считают $O(1)$

Простое правило для подсчёта времени

Считайте доминирующую часть:

• $O(n) + O(n)$ → $O(n)$
• $O(n) + O(n \log n)$ → $O(n \log n)$
• $O(n^2) + O(n)$ → $O(n^2)$

То есть складывать «точно» не нужно — важен самый быстро растущий член.

Память (space complexity)

Память — это сколько дополнительного места вы используете кроме входных данных.

Типичные случаи:

• Если вы создаёте Map на $n$ элементов, память обычно $O(n)$
• Если вы используете несколько переменных и указателей, память $O(1)$

В LeetCode чаще всего ценят время, но память тоже важна: многие оптимизации — это обмен «память ↔ скорость».

Практический шаблон ответа на интервью и в решениях

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

1. Переформулирую задачу своими словами
2. Опишу идею и паттерн
3. Скажу, какие структуры данных использую и почему
4. Пройдусь по шагам алгоритма
5. Назову крайние случаи
6. Дам оценку времени и памяти
7. Напишу код

Это же удобно использовать как структуру комментариев в решении.

Типичные ошибки новичков на LeetCode

1. Писать код, не прогнав примеры руками
2. Игнорировать ограничения и пытаться «в лоб»
3. Путать значения и индексы (особенно в задачах про пары)
4. Использовать дорогие операции в цикле
5. Не проверять крайние случаи (пустые входы, повторы)

Особенно для JS:

• shift() у массива обычно дорогой, для очереди лучше индекс head
• сравнение строк и работа со срезами (slice) внутри цикла может раздувать время до $O(n^2)$

Как тренироваться, чтобы был прогресс

Выберите режим, который можно выдержать 4–8 недель.

Рекомендованный минимум:

• 4–6 задач в неделю
• после решения — 5 минут на разбор: какой паттерн, какие крайние случаи, какой Big‑O

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

1. 1–2 паттерна в неделю
2. по 5–10 задач на паттерн
3. возвращаться к сложным через 7–14 дней

Если нужен готовый список тем и паттернов, полезно смотреть на дорожные карты, но решать важно осознанно, а не «просто закрывать задачи».

Справка по нотации Big‑O:

• Big O notation

Итог

• LeetCode проходится стабильным процессом: контракт → ограничения → базовое решение → паттерн → структура данных → крайние случаи → Big‑O → код
• Паттерны — ваш главный ускоритель
• Big‑O — ваш главный фильтр: проходит ли решение по ограничениям

В следующей статье курса мы начнём с самого частого набора инструментов: массивы, строки, Map/Set и паттерн hash map для индексов и частот.

Массивы и строки: два указателя, скользящее окно, префиксные суммы

Массивы и строки — самые частые типы входных данных на LeetCode. Для них есть три паттерна, которые дают максимум результата на Easy/Medium:

• Два указателя (two pointers)
• Скользящее окно (sliding window)
• Префиксные суммы (prefix sums)

В предыдущей статье курса мы договорились о рабочем процессе: контракт → ограничения → базовое решение → паттерн → структура данных → крайние случаи → Big-O. Здесь мы «заполним» самые частые паттерны конкретными шаблонами мышления и кода для JS/TS.

Почему эти паттерны так важны

Большая часть задач по массивам и строкам сводится к идее:

• мы двигаем границы (индексы) по данным и поддерживаем инвариант — условие, которое всегда верно
• мы избегаем вложенных циклов $O(n^2)$, превращая их в один проход $O(n)$

Ключ: вместо «перебирать все подмассивы» мы учимся двигать границы умно.

Небольшие особенности JS/TS, которые влияют на Big-O

• arr[i] — обычно $O(1)$
• push/pop — амортизированно $O(1)$
• shift() — обычно дорого, потому что сдвигает элементы (часто $O(n)$)
• slice/substring внутри цикла может незаметно превратить решение в $O(n^2)$ из-за копирования

Для строк в JS:

• индексация s[i] удобна, но строка неизменяемая
• частая конкатенация в цикле тоже может быть дорогой, лучше собирать в массив и делать join (если реально нужно строить новую строку)

Два указателя

Два указателя — это два индекса, которые движутся по массиву или строке по правилам задачи.

Есть два самых частых вида.

Указатели навстречу друг другу

Подходит, когда:

• нужно сравнивать «лево/право» (палиндром)
• массив отсортирован и вы ищете пару с суммой (классика)
• нужно «сжать» массив с двух сторон

Пример идеи для палиндрома:

1. l в начале, r в конце
2. пока l < r, сравниваем символы
3. если равны — сдвигаем оба
4. если нет — ответ false

Пример кода (Valid Palindrome-подобная логика, без фильтрации символов):

function isPalindromeSimple(s: string): boolean {
  let l = 0;
  let r = s.length - 1;

  while (l < r) {
    if (s[l] !== s[r]) return false;
    l++;
    r--;
  }

  return true;
}

Указатели в одном направлении

Подходит, когда:

• нужно пройти массив и что-то «отфильтровать/сжать» на месте
• нужно поддерживать расстояние между указателями

Классический пример: «удалить элементы по условию», «удалить дубликаты в отсортированном массиве».

Типовой шаблон:

• slow — куда записываем следующий «хороший» элемент
• fast — чем сканируем массив

function removeValue(nums: number[], val: number): number {
  let slow = 0;

  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      nums[slow] = nums[fast];
      slow++;
    }
  }

  return slow; // новая длина
}

Почему это $O(n)$:

• fast делает ровно один проход
• записи через slow тоже максимум $n$

Скользящее окно

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

В скользящем окне важно ответить:

• что такое окно (какой диапазон индексов)
• какой инвариант мы держим (например, «в окне нет повторов»)
• какое состояние окна мы храним (частоты в Map, набор в Set, текущая сумма)

Фиксированное окно

Окно всегда одной длины k.

Признаки:

• «подмассив длины k»
• «среднее/сумма/максимум на отрезке фиксированной длины»

Трюк: вместо пересчёта суммы каждый раз за $O(k)$, обновляем её за $O(1)$:

• добавили новый элемент справа
• вычли элемент, который вышел слева

Переменное окно

Окно меняет размер, потому что мы ищем:

• «самую длинную подстроку без повторов»
• «минимальную длину подмассива с суммой не меньше S»
• «количество подмассивов, удовлетворяющих условию» (иногда)

Пример: самая длинная подстрока без повторяющихся символов

Инвариант: в окне нет повторов.

Состояние окна: Set символов.

function lengthOfLongestSubstring(s: string): number {
  const set = new Set<string>();
  let l = 0;
  let best = 0;

  for (let r = 0; r < s.length; r++) {
    while (set.has(s[r])) {
      set.delete(s[l]);
      l++;
    }

    set.add(s[r]);
    best = Math.max(best, r - l + 1);
  }

  return best;
}

Почему это $O(n)$:

• r проходит строку один раз
• l тоже не откатывается назад, он максимум дойдёт до конца

Частая ошибка: сдвигать l «наугад» (например, только на 1), не восстанавливая инвариант до конца.

Важное ограничение переменного окна

Скользящее окно для задач «минимальная длина подмассива с суммой ≥ S» корректно работает, когда числа неотрицательные. Если в массиве есть отрицательные, «сумма окна» может уменьшаться при расширении — и простое правило «двигай l, пока условие выполнено» перестаёт быть надёжным. Для таких случаев часто нужен паттерн префиксных сумм + Map.

Префиксные суммы

Префиксная сумма — это заранее посчитанная сумма от начала массива до позиции.

Определение через массив pref длины n + 1:

• pref[0] = 0
• pref[i + 1] — сумма элементов nums[0] + nums[1] + ... + nums[i]

Это удобно, потому что сумму на отрезке [l..r] можно получить за $O(1)$.

Формула:

$$\text{sum}(l..r) = pref[r + 1] - pref[l]$$

Пояснение каждого элемента:

• $l$ — левый индекс отрезка
• $r$ — правый индекс отрезка
• $pref[x]$ — сумма первых $x$ элементов массива (от 0 до x-1)
• $pref[r+1]$ содержит сумму до r включительно
• вычитая $pref[l]$, мы «убираем» всё до l-1, остаётся сумма на [l..r]

Пример: Range Sum Query (Immutable)

class NumArray {
  private pref: number[];

  constructor(nums: number[]) {
    this.pref = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.pref[i + 1] = this.pref[i] + nums[i];
    }
  }

  sumRange(left: number, right: number): number {
    return this.pref[right + 1] - this.pref[left];
  }
}

Префиксные суммы + Map: количество подмассивов с суммой k

Это один из самых важных трюков для задач, где:

• нужно посчитать количество подмассивов
• в массиве могут быть отрицательные числа
• скользящее окно не подходит

Идея:

• пусть pref — текущая префиксная сумма до позиции i
• нам нужен старый префикс oldPref, такой что pref - oldPref = k
• значит oldPref = pref - k
• будем хранить в Map, сколько раз встречался каждый префикс

function subarraySum(nums: number[], k: number): number {
  const count = new Map<number, number>();
  count.set(0, 1);

  let pref = 0;
  let ans = 0;

  for (const x of nums) {
    pref += x;

    const need = pref - k;
    ans += count.get(need) ?? 0;

    count.set(pref, (count.get(pref) ?? 0) + 1);
  }

  return ans;
}

Почему это работает:

• мы для каждого pref мгновенно узнаём, сколько раз раньше встречался pref - k
• каждый такой случай соответствует подмассиву, который заканчивается «здесь» и имеет сумму k

Сложность:

• время обычно $O(n)$
• память $O(n)$ из-за Map

Как быстро выбирать паттерн по условию

Признак в условии	Чаще всего подходит	Типичное состояние	Частая ошибка
«палиндром», «с двух концов», «пара в отсортированном массиве»	два указателя навстречу	2 индекса	забыть сдвинуть правильный указатель
«удалить/сжать/перезаписать на месте»	два указателя в одном направлении	slow/fast	портить данные до того, как считали нужное
«самая длинная/короткая подстрока», «подмассив»	скользящее окно	Map/Set/сумма	не держать инвариант окна
«много запросов суммы на отрезке»	префиксные суммы	pref[]	перепутать индексы r+1 и l
«количество подмассивов с суммой k», есть отрицательные	префиксы + Map	Map<pref, freq>	забыть count.set(0, 1)

Рекомендуемые задачи на LeetCode

• Два указателя:
  • Valid Palindrome
  • Remove Duplicates from Sorted Array
• Скользящее окно:
  • Longest Substring Without Repeating Characters
  • Minimum Size Subarray Sum
• Префиксные суммы:
  • Range Sum Query - Immutable
  • Subarray Sum Equals K

Итог

• Два указателя — когда границы двигаются по понятным правилам, часто вместо вложенных циклов
• Скользящее окно — когда вы ищете лучший подотрезок и можете поддерживать инвариант окна, двигая l и r
• Префиксные суммы — когда нужны быстрые суммы на отрезке и особенно когда скользящее окно не работает (например, из-за отрицательных чисел)

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

Хеш‑таблицы и множества: частоты, группы, быстрый поиск

Map и Set в JS/TS — это ваш главный инструмент, чтобы превращать решения в один проход по данным. Если в прошлой статье мы двигали границы (два указателя, окно) и поддерживали состояние, то здесь мы разберём самое частое состояние окна и проходов: хеш‑таблицы и множества.

Эта тема закрывает типовые задачи:

• быстрый поиск «видели ли элемент»
• подсчёт частот
• сопоставление значение → индекс
• группировка элементов по ключу (например, анаграммы)

Что такое хеш‑таблица простыми словами

Хеш‑таблица — структура данных для операций по ключу:

• положить значение по ключу
• получить значение по ключу
• проверить, есть ли ключ

В JS/TS для этого чаще всего используют:

• Map<K, V> — универсальная таблица ключ → значение
• Set<T> — множество уникальных значений (по сути, Map без значений)

Почему это так популярно на LeetCode:

• средняя стоимость get/set/has обычно близка к $O(1)$

Пояснение формулы $O(1)$:

• $O(\cdot)$ — обозначение порядка роста (Big‑O)
• 1 — «константа», то есть время почти не зависит от размера входа

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

Map и Set в JS/TS: что важно помнить

Map vs обычный объект

Map удобнее для алгоритмов, потому что:

• ключами могут быть не только строки (например, числа, объекты)
• нет проблем с унаследованными ключами и прототипом
• есть понятные методы get, set, has, delete

Ссылки:

• MDN: Map
• MDN: Set

Типовые операции и их смысл

• map.set(key, value) — записать
• map.get(key) — прочитать (может вернуть undefined)
• map.has(key) — проверить существование ключа
• set.add(x) — добавить в множество
• set.has(x) — проверить наличие

Критичная деталь для подсчёта: используйте ?? 0.

const freq = new Map<string, number>();
const ch = 'a';
freq.set(ch, (freq.get(ch) ?? 0) + 1);

Базовый паттерн: частоты (frequency map)

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

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

Типовой алгоритм:

1. Создать Map для частот.
2. Один раз пройти по данным.
3. На каждом шаге увеличить счётчик.

Пример: проверка анаграммы через частоты

Задача: две строки — анаграммы, если у них одинаковые символы с одинаковыми частотами.

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const freq = new Map<string, number>();

  for (const ch of s) {
    freq.set(ch, (freq.get(ch) ?? 0) + 1);
  }

  for (const ch of t) {
    const left = (freq.get(ch) ?? 0) - 1;
    if (left < 0) return false;
    if (left === 0) freq.delete(ch);
    else freq.set(ch, left);
  }

  return freq.size === 0;
}

Почему это эффективно:

• один проход по s и один по t
• время около $O(n)$, где $n$ — длина строки
• память около $O(k)$, где $k$ — число разных символов

Пояснение $O(n)$:

• $n$ — размер входа
• $O(n)$ — число операций растёт примерно линейно вместе с входом

Ссылка на задачу:

• Valid Anagram

Паттерн: быстрый поиск «видели ли мы элемент» через Set

Формулировки:

• «есть ли дубликаты»
• «встречается ли элемент»
• «найти пересечение»

Пример: есть ли дубликаты

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();

  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }

  return false;
}

Ссылка на задачу:

• Contains Duplicate

Пример: пересечение двух массивов

Обычно выгодно строить Set по меньшему массиву.

function intersection(nums1: number[], nums2: number[]): number[] {
  const small = nums1.length <= nums2.length ? nums1 : nums2;
  const large = nums1.length <= nums2.length ? nums2 : nums1;

  const set = new Set<number>(small);
  const ans = new Set<number>();

  for (const x of large) {
    if (set.has(x)) ans.add(x);
  }

  return Array.from(ans);
}

Паттерн: значение → индекс (самая частая оптимизация)

Если задача звучит как:

• «найти два элемента, которые…»
• «вернуть индексы»

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

Пример: Two Sum

Идея:

• идём слева направо
• для текущего x хотим найти need = target - x
• если need уже встречался, значит у нас есть ответ

function twoSum(nums: number[], target: number): number[] {
  const indexByValue = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    const need = target - x;

    if (indexByValue.has(need)) {
      return [indexByValue.get(need)!, i];
    }

    indexByValue.set(x, i);
  }

  return [];
}

Что важно:

• мы добавляем x в Map после проверки, чтобы не использовать один и тот же элемент дважды

Ссылка:

• Two Sum

Паттерн: группировка по ключу

Формулировки:

• «сгруппировать»
• «одинаковые по свойству»
• «анаграммы в группы»

Шаблон:

1. Превратить элемент в ключ группы.
2. Map<key, group[]>.
3. Для каждого элемента: найти группу по ключу и добавить.

Пример: группировка анаграмм

Ключ группы: отсортированные буквы.

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();

  for (const s of strs) {
    const key = s.split('').sort().join('');
    const bucket = groups.get(key) ?? [];
    bucket.push(s);
    groups.set(key, bucket);
  }

  return Array.from(groups.values());
}

Комментарий про сложность:

• сам Map даёт быстрый доступ по ключу
• но построение ключа через сортировку даёт стоимость примерно $O(m \log m)$ на строку, где $m$ — её длина

Ссылка:

• Group Anagrams

Как Map/Set связываются со скользящим окном и префиксными суммами

Эти структуры данных чаще всего становятся состоянием, которое мы поддерживаем.

Типовые связки:

• скользящее окно + Set: в окне нет повторов (например, уникальная подстрока)
• скользящее окно + Map: частоты символов/чисел внутри окна
• префиксные суммы + Map: сколько раз встречалась префиксная сумма

Здесь важно уметь выбирать контейнер:

• если важна только проверка присутствия, обычно Set
• если нужны количества или дополнительные данные, обычно Map

Ссылки на задачи, где это центральная идея:

• Longest Substring Without Repeating Characters
• Subarray Sum Equals K

Частые ошибки в задачах с Map/Set

• Путать map.get(key) === undefined и отсутствие ключа: если значения могут быть undefined, проверяйте через map.has(key).
• Забывать базовое значение для счётчиков: используйте (map.get(key) ?? 0) + 1.
• Делать ключ группы неоднозначным: если «склеить» числа без разделителей, можно получить коллизии ключей.
• Не учитывать, что ключ в Map сравнивается по идентичности: два разных объекта {a:1} и {a:1} — это разные ключи.

Быстрый выбор подхода по условию

Признак в условии	Вероятный паттерн	Структура данных	Что хранить
«есть ли дубликаты», «видели ли элемент»	membership check	Set	увиденные значения
«сколько раз встречается»	частоты	Map	key -> count
«вернуть индексы пары»	значение → индекс	Map	value -> index
«сгруппировать по свойству»	группировка	Map	groupKey -> array

Рекомендуемые задачи на LeetCode

• Set для «видели ли элемент»:
  • Contains Duplicate
• Map для индексов:
  • Two Sum
• частоты:
  • Valid Anagram
• группировка:
  • Group Anagrams

Итог

• Set — для быстрого ответа на вопрос «есть ли элемент»
• Map — для частот, индексов и группировки
• большая часть оптимизаций на массивах и строках — это замена вложенных циклов на один проход, где состояние хранится в Map/Set

В следующих темах курса эти же структуры будут регулярно появляться внутри более «структурных» паттернов: стек, очередь, BFS/DFS и задачи на графы, где быстрое посещение вершин через Set и подсчёты через Map — базовая техника.

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

Связные списки, стек и очередь часто встречаются на LeetCode как входные данные или как внутренний инструмент решения. Если в прошлых статьях мы учились оптимизировать проходы по массивам/строкам (два указателя, окно, префиксы) и хранить состояние в Map/Set, то здесь вы получите базу для задач, где:

• нельзя (или невыгодно) индексироваться как в массиве
• нужно добавлять/удалять элементы строго с одного конца (стек) или с двух концов по правилам FIFO (очередь)
• важно не ошибиться с указателями, null и краевыми случаями

Когда эти структуры встречаются на LeetCode

• Связный список как вход: развернуть список, удалить n-й с конца, найти цикл, объединить два списка.
• Стек как идея: проверка скобок, обход выражений, монотонный стек для “следующий больший элемент”.
• Очередь как идея: BFS по уровням, кратчайшие шаги в невзвешенном графе, поток событий.

Мини-напоминание про сложность

В курсе мы используем Big-O для оценки скорости.

• $O(1)$ означает, что операция занимает примерно постоянное время и почти не зависит от размера входа.
• $O(n)$ означает, что время растёт примерно линейно.

Где:

• $n$ — размер входа (например, длина списка)
• $O(\cdot)$ — обозначение порядка роста времени

Связный список

Связный список состоит из узлов. Каждый узел хранит:

• значение val
• ссылку на следующий узел next

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

Базовая модель узла (JS/TS)

На LeetCode чаще всего дают ListNode уже готовым. Но полезно понимать, что внутри примерно так:

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

Главные ловушки со списками

• null в неожиданный момент: всегда проверяйте node !== null перед node.next.
• Потеря хвоста: если меняете next, заранее сохраните ссылку на “старый next”.
• Ошибка на длине 0/1: многие алгоритмы ломаются на пустом списке или одном узле.

Паттерн: итерация одним указателем

Мини-шаблон:

function traverse(head: ListNode | null): void {
  let cur = head;
  while (cur !== null) {
    // работа с cur.val
    cur = cur.next;
  }
}

Это линейный проход: $O(n)$ по времени и $O(1)$ по дополнительной памяти.

Паттерн: два указателя (slow/fast)

Это тот же принцип “два указателя”, который вы уже видели на массивах/строках, но теперь указатели двигаются по next.

Типовые применения:

• найти середину списка
• найти цикл (Floyd’s cycle detection)
• удалить n-й узел с конца (через разрыв дистанции между указателями)

Пример: есть ли цикл

Идея:

• slow двигается на 1 шаг
• fast двигается на 2 шага
• если есть цикл, они встретятся

function hasCycle(head: ListNode | null): boolean {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

Ловушка: условие цикла должно проверять и fast, и fast.next, иначе будет попытка обратиться к next у null.

Ссылка на задачу:

• Linked List Cycle

Паттерн: разворот списка (самая важная техника)

Разворот односвязного списка — это “тренажёр” на управление ссылками.

Инвариант:

• prev — голова уже развёрнутой части
• cur — текущий узел, который мы разворачиваем

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur: ListNode | null = head;

  while (cur !== null) {
    const next = cur.next; // сохранить, иначе потеряем хвост
    cur.next = prev;       // развернуть ссылку
    prev = cur;            // продвинуть prev
    cur = next;            // перейти к следующему узлу
  }

  return prev;
}

Типовая ловушка: поменять cur.next до того, как сохранили cur.next во временную переменную.

Ссылка на задачу:

• Reverse Linked List

Паттерн: фиктивный узел (dummy) для “удалений и слияний”

Когда нужно строить новый список (или аккуратно менять голову), часто создают “фиктивную голову”:

• это упрощает код: вы всегда добавляете в tail.next и не делаете отдельные ветки для первого элемента

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

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;

  let a = list1;
  let b = list2;

  while (a !== null && b !== null) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }

  tail.next = a ?? b;
  return dummy.next;
}

Ссылка на задачу:

• Merge Two Sorted Lists

Стек

Стек — структура LIFO:

• последним положили — первым достали

На LeetCode стек часто означает: “идём слева направо и храним незавершённый контекст”.

Стек в JS: Array как стек

Обычно достаточно массива:

• push — положить
• pop — снять

Справка:

• MDN: Array.prototype.push
• MDN: Array.prototype.pop

Пример: валидность скобок

Идея:

• открывающую скобку кладём в стек
• на закрывающей проверяем верх стека

function isValid(s: string): boolean {
  const st: string[] = [];
  const openToClose = new Map<string, string>([
    ['(', ')'],
    ['[', ']'],
    ['{', '}'],
  ]);

  for (const ch of s) {
    if (openToClose.has(ch)) {
      st.push(ch);
    } else {
      const top = st.pop();
      if (top === undefined) return false;
      if (openToClose.get(top) !== ch) return false;
    }
  }

  return st.length === 0;
}

Ловушки:

• попытка pop() из пустого стека
• забыть в конце проверить st.length === 0

Ссылка на задачу:

• Valid Parentheses

Монотонный стек как “следующий уровень”

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

Пока достаточно понимать идею:

• стек хранит кандидатов, которые ещё не нашли “ответ справа”
• когда приходит новый элемент, он “закрывает” часть стека

В следующих темах курса это будет регулярно встречаться.

Очередь

Очередь — структура FIFO:

• первым пришёл — первым ушёл

На LeetCode очередь чаще всего появляется в BFS и задачах “обрабатывай события в порядке поступления”.

Очередь в JS: не используйте shift() в цикле

Интуитивная реализация очереди через массив:

• push добавляет в конец
• shift удаляет из начала

Но у shift часто высокая стоимость, потому что нужно сдвигать элементы.

Справка:

• MDN: Array.prototype.shift

Вместо этого делайте “очередь с головой”:

• храните массив
• храните индекс head
• “вытаскивание” — это чтение q[head] и head++

class Queue<T> {
  private data: T[] = [];
  private head = 0;

  enqueue(x: T): void {
    this.data.push(x);
  }

  dequeue(): T | undefined {
    if (this.head >= this.data.length) return undefined;
    const x = this.data[this.head];
    this.head++;

    // необязательно, но полезно иногда чистить память
    if (this.head > 1024 && this.head * 2 > this.data.length) {
      this.data = this.data.slice(this.head);
      this.head = 0;
    }

    return x;
  }

  isEmpty(): boolean {
    return this.head >= this.data.length;
  }
}

Ловушки:

• забыть проверить пустоту очереди
• бесконтрольный рост массива, если никогда не “подрезать” обработанную часть

Как выбирать: массив, список, стек, очередь

Что нужно по условию	Почти всегда это	Как реализовать в JS/TS	Типичная ошибка
много вставок/удалений “в середине” структуры по ссылкам	связный список	ListNode и работа с next	потерять ссылку на следующий узел
“последнее действие отменить”, “вложенность”, “скобки”, “контекст”	стек	Array + push/pop	pop из пустого стека
“обработай в порядке поступления”, BFS	очередь	Array + head	использовать shift() в большом цикле
нужен быстрый доступ по индексу	массив	Array	пытаться “индексировать” список

Рекомендуемые задачи на LeetCode

• Связные списки:
  • Reverse Linked List
  • Linked List Cycle
  • Merge Two Sorted Lists
• Стек:
  • Valid Parentheses
• Очередь (идея полезна для BFS в следующих темах):
  • Number of Recent Calls

Итог

• Связный список требует аккуратной работы со ссылками: почти все ошибки — это потерянный next или неверная обработка null.
• Стек — ваш инструмент для задач на вложенность и “незавершённые состояния”; в JS он почти всегда делается через push/pop.
• Очередь для BFS и потока событий в JS лучше реализовывать через массив и индекс head, а не через shift().

Дальше эти структуры начнут комбинироваться с тем, что вы уже знаете: Map/Set для посещённых элементов и подсчётов, два указателя для “быстрого/медленного”, и очереди/стеки внутри обходов графов и деревьев.

Деревья и графы: DFS/BFS, рекурсия, обходы, кратчайшие пути

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

Связь с предыдущими статьями курса такая:

• Из статьи про массивы и строки вы уже знаете идею инварианта и аккуратного прохода.
• Из статьи про Map/Set вы берёте visited и частоты.
• Из статьи про стек и очередь вы берёте реализацию DFS через стек и BFS через очередь без shift().

Здесь мы соберём это в систему для деревьев и графов: DFS/BFS, рекурсия, виды обходов и кратчайшие пути.

Модели данных на LeetCode

Бинарное дерево

Обычно вам дают TreeNode:

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

Свойства дерева, которые важны для решений:

• В дереве нет циклов.
• У узла обычно есть ссылки на детей.
• Частые ответы: глубина, сумма, путь, значения по уровням.

Граф

Граф может прийти как:

• список рёбер edges.
• матрица (grid) m x n.
• объект-узлы с соседями.

Почти всегда удобнее думать в виде списка смежности:

• adj[u] хранит список соседей вершины u.

В отличие от дерева, в графе могут быть:

• циклы.
• несколько компонент связности.
• ориентированные рёбра.

DFS и BFS: что это и когда что выбирать

DFS (Depth-First Search)

DFS идёт в глубину.

Обычно выбирайте DFS, когда:

• нужно посчитать что-то по поддеревьям (глубина, сумма).
• нужен путь или проверка условия на пути.
• нужно обойти компоненту целиком.

DFS реализуется:

• рекурсией.
• стеком (итеративно).

BFS (Breadth-First Search)

BFS идёт по слоям.

Обычно выбирайте BFS, когда:

• нужен обход по уровням дерева.
• нужно найти минимальное количество шагов в невзвешенном графе.
• есть формулировки типа минимум ходов, shortest path (без весов).

BFS почти всегда реализуется очередью.

Рекурсия в деревьях: базовый шаблон

Главная идея рекурсии

Рекурсивная функция делает две вещи:

• описывает ответ для текущего узла через ответы для детей.
• корректно обрабатывает базовый случай null.

Шаблон:

function dfs(node: TreeNode | null): number {
  if (node === null) return 0; // базовый случай

  const left = dfs(node.left);
  const right = dfs(node.right);

  // собрать ответ из left/right и node.val
  return Math.max(left, right) + 1;
}

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

• left это глубина левого поддерева.
• right это глубина правого поддерева.
• + 1 это текущий узел.

Ссылка на типовую задачу:

• Maximum Depth of Binary Tree

Важная ловушка: глубина рекурсии в JS

В JavaScript рекурсия может упасть из-за ограничения стека вызовов на очень глубоких входах.

Практическое правило для LeetCode:

• Для деревьев обычно рекурсия проходит.
• Для графов или очень вытянутых структур держите в голове итеративный DFS (стек).

Обходы бинарного дерева

Для деревьев часто спрашивают порядок обхода.

DFS-обходы: preorder, inorder, postorder

• Preorder: узел → левое → правое.
• Inorder: левое → узел → правое.
• Postorder: левое → правое → узел.

Это важно, потому что разные задачи естественно выражаются разным обходом:

• Preorder удобен, когда вы хотите обработать узел до детей (например, построение копии).
• Postorder удобен, когда ответ для узла зависит от детей (например, высота, сумма).
• Inorder часто встречается в задачах на BST.

BFS-обход: level order

Level order возвращает значения по уровням и почти всегда делается BFS.

Классическая задача:

• Binary Tree Level Order Traversal

Пример BFS по уровням (очередь без shift()):

function levelOrder(root: TreeNode | null): number[][] {
  if (root === null) return [];

  const q: TreeNode[] = [root];
  let head = 0;
  const ans: number[][] = [];

  while (head < q.length) {
    const levelSize = q.length - head;
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = q[head++];
      level.push(node.val);

      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }

    ans.push(level);
  }

  return ans;
}

Почему работает levelSize = q.length - head:

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

Графы: ключевой элемент, которого нет в деревьях

visited: защита от циклов

В графе без visited вы можете уйти в бесконечный обход.

visited обычно это Set, где вы храните вершины, которые уже обработали.

• Для графа с вершинами-числами: Set<number>.
• Для grid: часто хранят r * cols + c.

Список смежности: как собрать из рёбер

Если дано edges: [u, v][] и граф неориентированный:

function buildUndirectedAdj(n: number, edges: number[][]): number[][] {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);
  }
  return adj;
}

Если граф ориентированный, добавляете только adj[u].push(v).

DFS в графе: рекурсивно и итеративно

Рекурсивный DFS

function dfsGraph(start: number, adj: number[][]): void {
  const visited = new Set<number>();

  function dfs(v: number): void {
    visited.add(v);
    for (const nei of adj[v]) {
      if (!visited.has(nei)) dfs(nei);
    }
  }

  dfs(start);
}

Итеративный DFS (стек)

function dfsGraphIter(start: number, adj: number[][]): void {
  const visited = new Set<number>();
  const st: number[] = [start];

  while (st.length > 0) {
    const v = st.pop()!;
    if (visited.has(v)) continue;
    visited.add(v);

    for (const nei of adj[v]) {
      if (!visited.has(nei)) st.push(nei);
    }
  }
}

Практическая разница:

• Итеративный DFS снижает риск падения из-за глубокой рекурсии.
• Но порядок обработки может отличаться, и это нормально, если задача не требует конкретного порядка.

BFS в графе: основа кратчайших путей без весов

Почему BFS даёт кратчайший путь

В невзвешенном графе каждый переход по ребру имеет одинаковую “цену” в 1 шаг.

BFS обходит граф слоями:

• сначала все вершины на расстоянии 1.
• потом на расстоянии 2.
• и так далее.

Поэтому первая встреча вершины в BFS гарантирует минимальное число шагов.

BFS с расстоянием

function shortestSteps(start: number, target: number, adj: number[][]): number {
  const q: number[] = [start];
  let head = 0;

  const dist = new Map<number, number>();
  dist.set(start, 0);

  while (head < q.length) {
    const v = q[head++];
    const d = dist.get(v)!;

    if (v === target) return d;

    for (const nei of adj[v]) {
      if (!dist.has(nei)) {
        dist.set(nei, d + 1);
        q.push(nei);
      }
    }
  }

  return -1;
}

Почему здесь можно использовать dist вместо отдельного visited:

• если вершина есть в dist, значит мы уже нашли для неё минимальную дистанцию и больше не хотим переоткрывать.

Типовые задачи:

• Shortest Path in Binary Matrix
• Rotting Oranges

Grid-задачи: деревья и графы в маске матрицы

Очень много задач про графы замаскированы под матрицу.

Идея:

• каждая клетка это вершина.
• рёбра это переходы вверх/вниз/влево/вправо (иногда диагонали).

DFS/BFS для количества островов

Это типовая задача на компоненты связности:

• Number of Islands

Мини-скелет (DFS), где visited нужен, чтобы не заходить в клетку дважды:

function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  const visited = new Set<number>();

  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  function id(r: number, c: number): number {
    return r * cols + c;
  }

  function dfs(r: number, c: number): void {
    visited.add(id(r, c));
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] !== '1') continue;
      const key = id(nr, nc);
      if (visited.has(key)) continue;
      dfs(nr, nc);
    }
  }

  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !visited.has(id(r, c))) {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

Ориентированные графы: топологическая сортировка и “зависимости”

Если в задаче есть формулировки:

• “можно ли закончить все курсы”
• “есть ли цикл зависимостей”
• “упорядочить задачи по prerequisites”

то это почти всегда ориентированный граф.

Классическая задача:

• Course Schedule

Что обычно делают:

• строят ориентированный граф prereq -> course.
• ищут цикл.

Два популярных подхода:

• DFS с состояниями (в обработке или обработан).
• BFS по входящим степеням (алгоритм Кана).

Здесь важно запомнить смысл состояний для DFS:

• visiting: вершина в текущем стеке рекурсии.
• visited: вершина полностью обработана.

Если при обходе вы попадаете в visiting, значит есть цикл.

Кратчайшие пути: что делать, если есть веса

Если у рёбер разные стоимости, BFS уже не гарантирует оптимальность.

Признаки “весов”:

• “время передачи”, “стоимость”, “цена”, “задержка”.
• ребро описывается как u, v, w, где w не всегда равен 1.

Тогда часто нужен алгоритм Дейкстры.

Для практики на LeetCode:

• Network Delay Time

Для фронтенд-разработчика полезная рамка выбора такая:

• веса нет или все переходы равны 1 шагу → BFS.
• веса разные и неотрицательные → обычно Дейкстра.

В этом курсе важнее уверенно делать BFS/DFS и понимать, почему BFS работает для “минимум шагов”. Дейкстру стоит брать следующей, когда BFS начинает “не проходить по смыслу”.

Шпаргалка выбора подхода

Формулировка в задаче	Чаще всего это	Подход	Состояние
“обойти всё”, “посчитать компоненту”, “есть ли путь”	граф/дерево	DFS	visited Set
“значения по уровням”, “глубина по слоям”	дерево	BFS	очередь
“минимум шагов”, “shortest path” без весов	граф/grid	BFS	очередь + dist
“зависимости”, “можно ли завершить”	ориентированный граф	DFS цикл или BFS по степеням	visiting/visited или indegree
“стоимость/время на ребре”	взвешенный граф	Дейкстра	dist + приоритетная очередь

Рекомендуемые задачи на LeetCode

Деревья:

• Maximum Depth of Binary Tree
• Binary Tree Level Order Traversal
• Invert Binary Tree
• Validate Binary Search Tree

Графы и grid:

• Number of Islands
• Rotting Oranges
• Shortest Path in Binary Matrix
• Clone Graph
• Course Schedule

Итог

• DFS это “в глубину”: рекурсией или стеком; идеален для поддеревьев, путей и компонент.
• BFS это “по слоям”: очередь; идеален для уровней и кратчайшего пути в невзвешенном графе.
• В графах почти всегда нужен visited, потому что возможны циклы.
• Grid-задачи это графы, где вершины это клетки.
• Если появляется стоимость ребра, BFS уже не подходит по смыслу: обычно нужен Дейкстра.

Динамическое программирование: состояния, переходы, оптимизации

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

Связь с предыдущими темами курса:

• Из статьи про Big-O вы берёте привычку заранее оценивать, пройдёт ли решение: DP чаще всего превращает перебор $O(2^n)$ в $O(n)$ или $O(n \cdot m)$.
• Из статей про массивы/строки и Map/Set вы берёте идею “держим состояние” и обновляем его за $O(1)$.
• Из статьи про деревья/графы вы уже видели рекурсию и visited; в DP похожая идея называется мемоизация (кэширование результатов подзадач).

Что такое DP простыми словами

DP работает, когда одновременно верны два свойства:

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

Главная мысль:

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

Как распознать DP по условию

Частые формулировки:

• “минимум/максимум” (стоимость, шаги, сумма, штраф)
• “количество способов” (сколькими путями, сколько раз, сколько вариантов)
• “можно ли” (достижимость, возможно ли набрать сумму, возможно ли дойти)
• “выбрать/не выбрать” (подмножество, ограниченный ресурс)

Частые структуры входа:

• индекс в массиве/строке
• координаты в матрице
• позиция + дополнительный параметр (например, “сколько ещё можно взять”, “последний выбранный”, “сколько ошибок допустимо”)

Чек-лист построения DP-решения

Чтобы DP не превращалось в магию, используйте один и тот же конструктор:

1. Определите состояние: что именно вы храните в dp.
2. Определите переход: как получить dp[state] из более простых dp[...].
3. Определите базовые случаи: самые маленькие состояния.
4. Определите порядок вычислений: сверху-вниз (рекурсия) или снизу-вверх (таблица).
5. Определите, где лежит ответ: dp[n], max(dp), dp[rows-1][cols-1] и т.д.
6. Оцените сложность: сколько состояний и сколько переходов на состояние.

Два основных стиля: memoization и tabulation

Memoization (сверху-вниз)

Вы пишете рекурсивную функцию solve(state) и кэшируете результат.

Плюсы:

• часто проще вывести переход
• вычисляете только нужные состояния

Минусы в JS/TS:

• можно упереться в ограничение глубины рекурсии
• нужен аккуратный ключ для кэша (Map)

Tabulation (снизу-вверх)

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

Плюсы:

• нет риска переполнить стек вызовов
• часто проще оптимизировать память

Минусы:

• иногда сложнее подобрать порядок

Практическое правило для LeetCode на JS:

• если глубина рекурсии может быть большой (например, длинный массив, граф-подобные состояния) — предпочтительнее tabulation.

Пример 1: “сколько способов” (Climbing Stairs)

Задача: Climbing Stairs.

Состояние

dp[i] — количество способов добраться до ступеньки i.

Переход

На i можно прийти:

• с i - 1 одним шагом
• с i - 2 двумя шагами

Поэтому:

$$dp[i] = dp[i - 1] + dp[i - 2]$$

Пояснение обозначений:

• $i$ — номер ступеньки
• $dp[i]$ — число способов попасть на ступеньку $i$
• $dp[i - 1]$ и $dp[i - 2]$ — уже посчитанные способы для предыдущих ступенек
• знак $+$ означает, что варианты “через шаг 1” и “через шаг 2” не пересекаются, их можно сложить

База

• dp[0] = 1 (стоять внизу — один способ)
• dp[1] = 1

Ответ

dp[n].

Реализация с оптимизацией памяти до $O(1)$

Таблица целиком не нужна: dp[i] зависит только от двух предыдущих.

function climbStairs(n: number): number {
  if (n <= 1) return 1;

  let a = 1; // dp[i-2]
  let b = 1; // dp[i-1]

  for (let i = 2; i <= n; i++) {
    const c = a + b; // dp[i]
    a = b;
    b = c;
  }

  return b;
}

Сложность:

• время $O(n)$: один цикл до n
• память $O(1)$: фиксированное число переменных

Пример 2: “минимальная стоимость” (Min Cost Climbing Stairs)

Задача: Min Cost Climbing Stairs.

Состояние

dp[i] — минимальная стоимость, чтобы оказаться на “платформе” i.

Удобная модель: пусть i — это позиция, куда вы приходите, а платить нужно за ступеньку, на которую наступили.

Переход

Чтобы попасть на i, вы приходите:

• с i - 1, заплатив cost[i - 1]
• с i - 2, заплатив cost[i - 2]

Тогда:

$$dp[i] = \min(dp[i-1] + cost[i-1],\ dp[i-2] + cost[i-2])$$

Пояснение обозначений:

• $dp[i]$ — минимальная стоимость достижения позиции $i$
• $cost[j]$ — цена ступеньки $j$
• функция $\min(\cdot)$ выбирает более дешёвый из двух вариантов

База и ответ

• dp[0] = 0, dp[1] = 0 (стартовать можно с 0 или 1 без оплаты)
• ответ dp[n], где n = cost.length

Реализация (rolling array)

function minCostClimbingStairs(cost: number[]): number {
  const n = cost.length;
  let a = 0; // dp[i-2]
  let b = 0; // dp[i-1]

  for (let i = 2; i <= n; i++) {
    const one = b + cost[i - 1];
    const two = a + cost[i - 2];
    const cur = Math.min(one, two);
    a = b;
    b = cur;
  }

  return b;
}

Самая важная идея про “состояние”: оно должно быть минимальным

Новички часто делают состояние слишком большим:

• “пусть dp хранит весь путь”
• “пусть dp хранит весь набор выбранных элементов”

Это почти всегда взрывает память.

Правило:

• состояние должно хранить ровно то, без чего нельзя построить переход.

Пример “минимального” состояния:

• “где я сейчас” (i)
• “какой ресурс остался” (cap)
• “какой параметр влияет на будущее” (last, k, mask)

Частые формы DP на LeetCode

DP по индексу (1D)

Признаки:

• двигаемся слева направо
• на каждом шаге выбираем “взять/не взять” или “прыгнуть/не прыгнуть”

Типовые задачи:

• House Robber
• Maximum Subarray (часто решают как DP/Кадане)

Мини-идея House Robber:

• dp[i] — максимум денег на префиксе до i
• переход: либо не брать i, либо взять i и тогда нельзя брать i-1

DP по сетке (2D)

Признаки:

• матрица rows x cols
• можно двигаться по допустимым направлениям
• нужно посчитать количество путей или минимальную сумму

Типовые задачи:

• Unique Paths
• Minimum Path Sum

Шаблон состояния:

• dp[r][c] — ответ для клетки (r, c)

Обычно переход берёт минимум/сумму из dp[r-1][c] и dp[r][c-1].

“Рюкзак”: DP по ресурсу (0/1 и unbounded)

Признаки:

• есть ограничение (вес, время, бюджет)
• нужно максимизировать ценность или проверить достижимость

Классические темы:

• 0/1 knapsack: каждый предмет можно взять 0 или 1 раз
• unbounded knapsack: предмет можно брать много раз

На LeetCode это часто выглядит как задачи про суммы/монеты:

• Coin Change (минимум монет)

Очень важно для оптимизации памяти:

• в 0/1 варианте обычно итерируются по ресурсу в обратном порядке, чтобы не использовать предмет дважды
• в unbounded варианте обычно итерируются в прямом порядке

Оптимизации DP, которые реально нужны на LeetCode

Оптимизация памяти: “rolling array”

Если переход использует только предыдущий слой (например, только i-1), можно хранить 1–2 строки/массива вместо всей таблицы.

Типовой сигнал:

• dp[i] зависит только от dp[i-1], dp[i-2] → храните 2 переменные
• dp[i][j] зависит только от dp[i-1][...] → храните 2 строки

Оптимизация до 1D в задачах “рюкзака”

Часто dp[item][cap] можно сжать в dp[cap].

Ключевая ловушка:

• неправильное направление цикла по cap меняет смысл (0/1 превращается в unbounded или наоборот)

Выбор структуры кэша: массив или Map

• Если состояния индексируются целыми числами и диапазон плотный: используйте Array.
• Если состояние сложное (пара координат, несколько параметров): используйте Map.

Для ключа в Map часто делают строку:

• key = i + ',' + cap

Это не самая быстрая техника, но на Medium часто проходит. Если нужна скорость, лучше кодировать в одно число (например, i * (CAP + 1) + cap).

Не путайте DP и BFS по состояниям

Иногда задача выглядит как “минимум шагов”, и рука тянется к DP, но правильнее BFS:

• если каждое действие имеет одинаковую стоимость 1, и состояние — вершина графа, то BFS найдёт минимум шагов напрямую

DP чаще применяют, когда:

• есть “естественный порядок” подзадач
• или граф состояний ацикличен (DAG)

Частые ошибки новичков в DP

• Состояние не соответствует смыслу задачи (неясно, что означает dp[i]).
• Нет базовых случаев, из-за чего всё становится undefined.
• Переход использует “будущие” значения (неверный порядок вычисления в tabulation).
• В 1D-оптимизации выбран неправильный порядок цикла.
• Мемоизация без ограничения: ключи разрастаются, а состояний слишком много.

Рекомендуемые задачи на LeetCode

Стартовые 1D:

• Climbing Stairs
• House Robber

Сетка:

• Unique Paths
• Minimum Path Sum

Ресурс/монеты:

• Coin Change

Справка:

• Dynamic programming

Итог

• DP строится по конструктору: состояние → переход → база → порядок → ответ.
• Два основных стиля: memoization (рекурсия + кэш) и tabulation (таблица).
• Главные практические оптимизации: rolling array, сжатие 2D в 1D, правильное направление циклов.
• Самый надёжный способ не ошибиться: сначала словами определить, что означает dp[state], и только потом писать код.

Повторение и стратегия: миксы тем, тайм‑менеджмент, разбор решений

Эта статья — “клей” курса. Вы уже познакомились с базовыми паттернами (два указателя, окно, префиксы), контейнерами (Map/Set), связными списками/стеком/очередью, обходами деревьев и графов (DFS/BFS), а также с динамическим программированием.

Дальше на LeetCode начинается самое важное: задачи почти никогда не “про одну тему”. Они проверяют, умеете ли вы:

• распознать паттерн в новом условии
• смешать 2–3 идеи в одно решение
• управлять временем, не выгорая
• разбирать чужие решения так, чтобы реально ускоряться

Ниже — рабочая стратегия для фронтенд‑разработчика: как тренироваться стабильно, как делать миксы тем, и как учиться на редакториалах и обсуждениях.

Что значит “уметь решать LeetCode” на практике

Умение — это не “решить прямо сейчас без подсказок”. Это более прикладная вещь:

• вы быстро переводите условие в контракт (что на входе, что на выходе, какие ограничения)
• вы быстро проверяете 3–5 краевых случаев
• вы узнаёте “скелет” решения (паттерн) и собираете код
• вы держите под контролем сложность и не пишете $O(n^2)$ там, где нужно $O(n)$
• вы умеете учиться на разборе: один раз ошиблись — больше так не делаете

Миксы тем: как задачи реально выглядят на LeetCode

В начале курса темы выглядели “отдельно”. В реальности они почти всегда соединяются. Ваша цель — научиться узнавать типовые связки.

Таблица: частые комбинации и что в них держать “в голове”

Комбинация	Как узнать по условию	Типичное “состояние”	Частая ошибка
Скользящее окно + Map	“самая длинная/короткая подстрока”, “ровно/не более K”	Map<символ, частота> или счётчик “плохих”	двигать l, не восстанавливая инвариант окна
Префиксные суммы + Map	“количество подмассивов”, “сумма k”, есть отрицательные	Map<prefixSum, сколько раз>	забыть начальное 0 -> 1
BFS + Set/Map	“минимум шагов”, grid, “дойти”	visited или dist	использовать shift() и получить TLE в JS
DFS + стек/рекурсия + Set	“обойти компоненту”, “острова”, “проверить связность”	visited	не помечать посещение вовремя и заходить повторно
Дерево DFS + возврат значения	“глубина”, “сумма”, “максимум”, “валидировать”	возвращаемое значение из dfs(node)	смешивать “глобальный ответ” и “возврат” без ясного смысла
DP + массив/Map	“максимум/минимум”, “количество способов”, повторяющиеся подзадачи	dp[i] или dp[state]	состояние слишком большое, нет ясного смысла dp

Смысл таблицы: не учить “100 задач”, а выучить “10 связок”, которые повторяются.

Как распознавать паттерны быстрее: метод “сигнальных слов”

Вместо того чтобы читать условие как историю, вы ищете сигналы.

1. Если видите “подстрока/подмассив”, первым делом спросите: это “лучший отрезок”?
2. Если “минимум шагов” и переходы равны — это почти всегда BFS.
3. Если “посчитать количество” чего-то по отрезкам — часто префиксы + Map.
4. Если “вернуть индексы/пару” — часто Map<value, index>.
5. Если “максимум/минимум/способы” и решение “наращивается” — проверяйте DP.

Полезно держать открытым список задач одного плана и делать их “пачкой”, например: Top Interview 150.

Тайм‑менеджмент: как заниматься, чтобы не бросить

Важнее всего — режим, который вы реально выдержите 4–8 недель.

Базовый недельный план (для занятых)

1. 4–5 дней в неделю по 35–60 минут.
2. 1 день — только разбор старых ошибок (без новых задач).
3. 1 день — отдых.

Почему это работает:

• вы регулярно “встречаете” паттерны
• вы оставляете время на разбор, который и даёт прирост

Структура одного занятия (таймбокс)

1. 3–5 минут: контракт, ограничения, крайние случаи.
2. 15–25 минут: самостоятельная попытка.
3. 10–20 минут: подсказка или редакториал, если не идёт.
4. 5–10 минут: переписать финальную версию аккуратно.
5. 3–5 минут: заметка “что выучил/где ошибся”.

Здесь важна дисциплина: если вы “залипаете” на 2 часа без прогресса, вы тренируете не навыки, а усталость.

Правила “когда смотреть подсказку”

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

1. Если через 10–15 минут вы всё ещё не можете назвать паттерн.
2. Если паттерн понятен, но вы не можете вывести переход/инвариант.
3. Если вы написали код, но не можете починить баг за 10 минут.

Где смотреть:

• редакториал задачи на LeetCode (если доступен)
• обсуждения: LeetCode Discuss

Система повторения: как не забывать решённое

Решить один раз — почти бесполезно. Полезно — закрепить.

Простая схема повторений

1. Повтор 1: через 2 дня — решить заново “по памяти” или по своему конспекту.
2. Повтор 2: через 7 дней — решить снова, но уже быстрее и чище.
3. Повтор 3: через 14 дней — решить в условиях “как на интервью” (таймер + объяснение).

Не нужно повторять всё. Повторяйте только задачи, где:

• вы подсматривали решение
• вы делали типичную ошибку (инвариант окна, visited, база в DP)
• вы долго кодили “механику” (очередь, разворот списка, обход дерева)

Как разбирать решения так, чтобы это давало рост

Разбор — это не “прочитал и забыл”. Нужна структура.

Чек‑лист разбора после принятого решения

1. Паттерн: как назвать одним словом основу решения?
2. Инвариант: что должно быть истинно на каждом шаге?
3. Состояние: что именно хранится в Map/Set/dp и почему?
4. Краевые случаи: на каких входах решение могло упасть?
5. Сложность: что доминирует по времени и памяти?
6. “Урок”: какую одну фразу вы унесёте в заметки?

Как сравнивать своё решение с чужим

В обсуждениях вы увидите разные стили. Сравнивать нужно не “красоту”, а инженерные свойства.

1. Сравните асимптотику: есть ли улучшение класса сложности или только микро‑оптимизация.
2. Сравните устойчивость: какой вариант лучше покрывает крайние случаи.
3. Сравните ясность инварианта: можно ли объяснить решение за 60 секунд.
4. Сравните риск ошибок в JS:

• есть ли shift() в BFS
• есть ли slice() внутри цикла по строке
• не создаются ли гигантские строки конкатенацией

Если чужое решение лучше, перепишите задачу в своём стиле и добавьте в повтор.

Шаблон заметок (короткий, но полезный)

Храните заметки не как “простыню”, а как карточки.

1. Название задачи + ссылка.
2. Паттерн: например, “скользящее окно + частоты”.
3. Инвариант одной строкой.
4. Состояние окна/обхода: что храню и как обновляю.
5. Одна типичная ошибка (ваша) и как вы её исправили.

Этого достаточно, чтобы через неделю восстановить решение за 5 минут.

Стратегия на интервью: тренируйте “объяснение”, а не только код

На собеседовании важно не только написать решение, но и проговорить.

Полезный шаблон речи (он же из первой статьи курса):

1. Переформулирую задачу и уточняю контракт.
2. Называю ограничения и что они требуют по сложности.
3. Называю паттерн.
4. Объясняю инвариант и состояние.
5. Прогоняю пример руками.
6. Говорю Big‑O.
7. Пишу код.

Чтобы это стало привычкой, раз в неделю делайте “сессию интервью”:

• 1 задача Medium
• таймер 35–45 минут
• вслух объясняете, что делаете

Практическая стратегия “смешанной недели”

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

Пример недели:

1. День 1: массив/строка (окно или два указателя).
2. День 2: Map/Set (частоты, группы или префиксы + Map).
3. День 3: стек или очередь (монотонный стек или BFS‑очередь).
4. День 4: дерево/граф (DFS/BFS).
5. День 5: DP (1D или grid).
6. День 6: разбор ошибок и повтор.

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

Итог

• Реальные задачи LeetCode — это миксы: учитесь узнавать связки (окно + Map, BFS + visited, префиксы + Map, DFS + возврат значения, DP с ясным состоянием).
• Прогресс даёт не количество задач, а цикл: попытка → подсказка → переписать → разбор → повтор.
• Таймбокс и повторение через 2/7/14 дней защищают от выгорания и забывания.
• Разбор чужих решений полезен только если вы фиксируете: паттерн, инвариант, состояние, типичную ошибку.