# Полные условия всех задач — Yandex Codenv, этап алгоритмов Файл собран через LeetCode GraphQL API. Сгруппированы по категориям из письма рекрутера. --- # MUST HAVE ## 1. Two Pointers ### Container With Most Water (Medium) Дан массив `height` длины `n`. Каждая `height[i]` — высота вертикальной линии в точке `i`. Найти две линии, которые с осью X образуют контейнер с максимальным количеством воды. Площадь = `min(height[i], height[j]) * (j - i)`. ``` Input: height = [1,8,6,2,5,4,8,3,7] → Output: 49 Input: height = [1,1] → Output: 1 ``` Constraints: `2 <= n <= 10^5`, `0 <= height[i] <= 10^4`. **Ключ:** два указателя с краёв, двигать меньшую высоту. O(n). ### Partition Labels (Medium) Разбить строку на максимальное число частей так, чтобы каждая буква была только в одной части. ``` Input: s = "ababcbacadefegdehijhklij" → Output: [9,7,8] Input: s = "eccbbbbdec" → Output: [10] ``` Constraints: `1 <= s.length <= 500`, lowercase English letters. **Ключ:** last occurrence map + второй проход: `end = max(end, last[s[i]])`, когда `i == end` — граница. ### Squares of a Sorted Array (Easy) Отсортированный массив (могут быть отрицательные). Вернуть массив квадратов, тоже отсортированный. **Follow-up: O(n) без sort().** ``` Input: nums = [-4,-1,0,3,10] → Output: [0,1,9,16,100] Input: nums = [-7,-3,2,3,11] → Output: [4,9,9,49,121] ``` Constraints: `1 <= n <= 10^4`, `-10^4 <= nums[i] <= 10^4`. **Ключ:** два указателя с краёв, заполнять результат с конца. ### Summary Ranges (Easy) Отсортированный уникальный массив → список диапазонов: `"a->b"` если больше одного, `"a"` если одно. ``` Input: nums = [0,1,2,4,5,7] → Output: ["0->2","4->5","7"] Input: nums = [0,2,3,4,6,8,9] → Output: ["0","2->4","6","8->9"] ``` Constraints: `0 <= n <= 20`. **Ключ:** один проход, хранить `start`. Когда разрыв — закрыть диапазон. --- ## 2. Hash Table ### Two Sum (Easy) Массив + target. Вернуть индексы двух чисел, дающих сумму = target. Ровно одно решение. ``` Input: nums = [2,7,11,15], target = 9 → Output: [0,1] Input: nums = [3,2,4], target = 6 → Output: [1,2] Input: nums = [3,3], target = 6 → Output: [0,1] ``` Constraints: `2 <= n <= 10^4`, `-10^9 <= nums[i] <= 10^9`. **Follow-up: < O(n²).** **Ключ:** `Hash` — значение → индекс, один проход. ### Valid Anagram (Easy) Вернуть true, если `t` — анаграмма `s`. ``` Input: s = "anagram", t = "nagaram" → true Input: s = "rat", t = "car" → false ``` Constraints: `1 <= length <= 5*10^4`, lowercase English. **Follow-up:** Unicode? **Ключ:** `Array.new(26, 0)` или `s.chars.tally == t.chars.tally`. ### Group Anagrams (Medium) Сгруппировать анаграммы вместе. ``` Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]] ``` Constraints: `1 <= n <= 10^4`, `0 <= len <= 100`. **Ключ:** отсортированная строка как ключ hash, либо `chars.tally`. ### Subarray Sum Equals K (Medium) Количество подмассивов с суммой = k. ``` Input: nums = [1,1,1], k = 2 → 2 Input: nums = [1,2,3], k = 3 → 2 ``` Constraints: `1 <= n <= 2*10^4`, `-1000 <= nums[i] <= 1000`, `-10^7 <= k <= 10^7`. **Ключ:** префикс-суммы + `Hash.new(0)` со счётчиком. `hash[0] = 1` — базовый случай! ### Find All Anagrams in a String (Medium) Найти все начальные индексы анаграмм `p` в `s`. ``` Input: s = "cbaebabacd", p = "abc" → [0,6] Input: s = "abab", p = "ab" → [0,1,2] ``` Constraints: `1 <= length <= 3*10^4`, lowercase English. **Ключ:** скользящее окно + `Array.new(26, 0)` для сравнения частот. ### Permutation in String (Medium) Содержит ли s2 перестановку s1? ``` Input: s1 = "ab", s2 = "eidbaooo" → true ("ba") Input: s1 = "ab", s2 = "eidboaoo" → false ``` Constraints: `1 <= length <= 10^4`. **Ключ:** то же, что Find All Anagrams, но остановиться на первом совпадении. ### Single Number (Easy) Каждый элемент появляется дважды, кроме одного. Найти его. **O(n) время, O(1) память.** ``` Input: nums = [2,2,1] → 1 Input: nums = [4,1,2,1,2] → 4 ``` Constraints: `1 <= n <= 3*10^4`. **Ключ:** XOR! `nums.reduce(:^)`. Без этого — не O(1) по памяти. --- ## 3. Sort ### Merge Intervals (Medium) Слить все пересекающиеся интервалы. ``` Input: intervals = [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] Input: intervals = [[1,4],[4,5]] → [[1,5]] ``` Constraints: `1 <= n <= 10^4`, `0 <= start <= end <= 10^4`. **Ключ:** `sort_by(&:first)`, затем один проход со слиянием. --- ## 4. Queue / Stack ### Valid Parentheses (Easy) Проверить правильность скобок `()[]{}`. ``` Input: s = "()" → true Input: s = "()[]{}" → true Input: s = "(]" → false Input: s = "([])" → true Input: s = "([)]" → false ``` Constraints: `1 <= length <= 10^4`. **Ключ:** стек через массив: `stack << c` / `stack.pop`. Хэш для пар скобок. --- ## 5. Sliding Window ### Sliding Window Maximum (Hard) Скользящее окно размера k. Вернуть максимум для каждого положения окна. ``` Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Пояснение: [1 3 -1] -3 5 3 6 7 → 3 1 [3 -1 -3] 5 3 6 7 → 3 1 3 [-1 -3 5] 3 6 7 → 5 1 3 -1 [-3 5 3] 6 7 → 5 1 3 -1 -3 [5 3 6] 7 → 6 1 3 -1 -3 5 [3 6 7] → 7 ``` Constraints: `1 <= n <= 10^5`, `-10^4 <= nums[i] <= 10^4`, `1 <= k <= n`. **Ключ:** монотонная deque (по убыванию). В Ruby — массив + ручное управление с двух концов: удалять индексы вне окна с головы, удалять элементы меньше текущего с хвоста. ### Sliding Window Median (Hard) То же, но вернуть медиану для каждого окна. Если чётное число элементов — среднее двух средних. ``` Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0] ``` Constraints: `1 <= k <= n <= 10^5`, `-2^31 <= nums[i] <= 2^31-1`. **Ключ:** две кучи (max-heap для меньшей половины, min-heap для большей) + ленивое удаление. Либо отсортированный массив + бинарный поиск для вставки/удаления (проще на Ruby, но O(n*k) в худшем случае против O(n log k)). --- ## 6. Iterator ### Peeking Iterator (Medium) Реализовать итератор с `peek()` — возвращает следующий элемент, не сдвигая указатель. ``` PeekingIterator.new([1,2,3]) next() → 1 peek() → 2 # указатель не сдвинут next() → 2 next() → 3 hasNext() → false ``` Constraints: `1 <= n <= 1000`, максимум 1000 вызовов. **Ключ:** кэшировать следующий элемент: `@next_val`, `@has_next`. `peek` возвращает кэш, `next` возвращает кэш и обновляет его. --- ## 7. Greedy ### Best Time to Buy and Sell Stock (Easy) Одна транзакция: купить в один день, продать в другой (позже). Максимальная прибыль. ``` Input: prices = [7,1,5,3,6,4] → 5 (купить за 1, продать за 6) Input: prices = [7,6,4,3,1] → 0 (нет прибыли) ``` Constraints: `1 <= n <= 10^5`, `0 <= prices[i] <= 10^4`. **Ключ:** один проход: `min_price`, `max_profit = max(max_profit, price - min_price)`. ### Best Time to Buy and Sell Stock II (Medium) Сколько угодно транзакций, но не больше одной акции одновременно. ``` Input: prices = [7,1,5,3,6,4] → 7 (1→5 + 3→6) Input: prices = [1,2,3,4,5] → 4 Input: prices = [7,6,4,3,1] → 0 ``` Constraints: `1 <= n <= 3*10^4`, `0 <= prices[i] <= 10^4`. **Ключ:** суммировать все `max(0, prices[i] - prices[i-1])`. Каждый подъём — транзакция. ### Best Time with Transaction Fee (Medium) Сколько угодно транзакций, но за каждую — комиссия `fee`. ``` Input: prices = [1,3,2,8,4,9], fee = 2 → 8 // (8-1-2) + (9-4-2) = 8 ``` Constraints: `1 <= n <= 5*10^4`, `1 <= prices[i] < 5*10^4`, `0 <= fee < 5*10^4`. **Ключ:** DP с двумя состояниями: `hold` (макс. прибыль, если держим акцию) и `cash` (если не держим). --- # ДОПОЛНИТЕЛЬНАЯ ТРЕНИРОВКА ## Linked Lists ### Merge K Sorted Lists (Hard) Слить k отсортированных связных списков в один. ``` Input: lists = [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6] ``` **Ключ:** min-heap (приоритетная очередь) по первому элементу каждого списка. ### Reverse Linked List (Easy) Развернуть связный список. ``` Input: head = [1,2,3,4,5] → [5,4,3,2,1] ``` **Ключ:** prev/curr/next, итеративно. **Follow-up:** рекурсивно. ## DFS/BFS ### Number of Islands (Medium) Дана сетка m×n из '1' (земля) и '0' (вода). Посчитать количество островов (земля, соединённая по горизонтали/вертикали). ``` Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] → 1 ``` Constraints: `1 <= m,n <= 300`. **Ключ:** DFS/BFS, помечать посещённые '1' как '0' (in-place). ### Remove Invalid Parentheses (Hard) Удалить минимальное число скобок, чтобы строка стала валидной. Вернуть все уникальные варианты. ``` Input: s = "()())()" → ["(())()","()()()"] Input: s = "(a)())()" → ["(a())()","(a)()()"] Input: s = ")(" → [""] ``` Constraints: `1 <= length <= 25`, максимум 20 скобок. **Ключ:** BFS по уровням (количество удалений). Или DFS с подсчётом лишних скобок. ## Heap / Hash ### Top K Frequent Words (Medium) Вернуть k самых частых слов. При равной частоте — лексикографически. ``` Input: words = ["i","love","leetcode","i","love","coding"], k = 2 Output: ["i","love"] ``` Constraints: `1 <= n <= 500`. **Follow-up:** O(n log k). **Ключ:** `tally`, затем сортировка по `[-count, word]` и взять первые k. Для O(n log k) — min-heap размера k. ## Binary Search ### Binary Search (Easy) Классический бинарный поиск в отсортированном массиве. O(log n). ``` Input: nums = [-1,0,3,5,9,12], target = 9 → 4 Input: nums = [-1,0,3,5,9,12], target = 2 → -1 ``` **Ключ:** `l, r = 0, n-1; while l <= r`, mid. ## Tree ### Same Tree (Easy) Одинаковы ли два бинарных дерева? ``` Input: p = [1,2,3], q = [1,2,3] → true Input: p = [1,2], q = [1,null,2] → false ``` **Ключ:** рекурсия: `p.val == q.val && same(p.left, q.left) && same(p.right, q.right)`. ### Symmetric Tree (Easy) Симметрично ли дерево относительно центра? ``` Input: root = [1,2,2,3,4,4,3] → true Input: root = [1,2,2,null,3,null,3] → false ``` **Ключ:** рекурсивно сравнить `left.left` с `right.right` и `left.right` с `right.left`. ### Subtree of Another Tree (Easy) Является ли `subRoot` поддеревом `root`? ``` Input: root = [3,4,5,1,2], subRoot = [4,1,2] → true ``` **Ключ:** для каждого узла root проверить `same_tree(root_node, subRoot)`. ### Find Duplicate Subtrees (Medium) Найти все дублирующиеся поддеревья. ``` Input: root = [1,2,3,4,null,2,4,null,null,4] → [[2,4],[4]] ``` Constraints: до 5000 узлов. **Ключ:** сериализовать каждое поддерево в строку, хранить в hash счётчик. ## Math / String Simulation ### Add Binary (Easy) Сложить две бинарные строки. ``` Input: a = "11", b = "1" → "100" Input: a = "1010", b = "1011" → "10101" ``` ### Add Strings (Easy) Сложить два числа-строки **без** преобразования в Integer. ``` Input: num1 = "11", num2 = "123" → "134" Input: num1 = "456", num2 = "77" → "533" ``` ### Multiply Strings (Medium) Перемножить два числа-строки **без** BigInteger и прямого преобразования. ``` Input: num1 = "2", num2 = "3" → "6" Input: num1 = "123", num2 = "456" → "56088" ``` Constraints: `1 <= length <= 200`. **Ключ:** умножение в столбик. Массив `result[i+j+1]` для хранения промежуточных цифр.