Модернизация алгоритмов: От наивного → оптимального

🔸Two Sum (пара с заданной суммой)
Наивно: O(n²) — двойной цикл
Оптимально: O(n) с использованием HashMap

🔸Find Duplicate Number (найти дубликат, 1 ≤ num ≤ n)
Наивно: HashSet или дополнительная память
Оптимально: Обнаружение цикла Флойда (O(1) по памяти)

🔸Kth Largest Element (k-й по величине элемент)
Наивно: Сортировка массива (O(n log n))
Оптимально: QuickSelect (в среднем O(n)) или куча (Heap)

🔸Longest Palindromic Substring (длиннейшая палиндромная подстрока)
Наивно: O(n³) — перебор всех подстрок
Оптимально: Расширение из центра (Expand Around Center, O(n²)), или алгоритм Манакера (O(n))

🔸Max Subarray Sum (максимальная сумма подмассива)
Наивно: Генерация всех подмассивов
Оптимально: Алгоритм Кадане (Kadane’s Algorithm, O(n))

🔸All Pairs Shortest Paths (кратчайшие пути между всеми вершинами)
Наивно: Запускать Dijkstra для каждой вершины
Оптимально: Алгоритм Флойда–Уоршелла (Floyd-Warshall, O(V³)), эффективен для плотных графов

🔸Median in Data Stream (медиана в потоке данных)
Наивно: Сортировать после каждой вставки
Оптимально: Две кучи (Min Heap и Max Heap), вставка за O(log n)

🔸Valid Anagram (анаграмма?)
Наивно: Сортировка строк
Оптимально: Подсчёт частот символов в массиве (O(n))

🔸Permutations (перестановки)
Наивно: Сгенерировать и сохранить все перестановки
Оптимально: Рекурсивный Backtracking с отсечениями

🔸Subset Sum Exists (проверка, существует ли сумма из подмножества)
Наивно: Перебор всех подмножеств (2ⁿ)
Оптимально: Динамическое программирование — снизу вверх или с мемоизацией

🔸Product of Array Except Self (произведение всех кроме текущего)
Наивно: Умножать все кроме текущего, O(n²)
Оптимально: Префикс + суффикс произведения (O(n))

🔸Shortest Unsorted Subarray (самый короткий несортированный подмассив)
Наивно: Сортировка и сравнение
Оптимально: Два указателя для границ (O(n))

🔸Min Window Substring (минимальная подстрока с нужными символами)
Наивно: Перебор всех подстрок
Оптимально: Sliding Window + HashMap, O(n)

🔸Search in Rotated Array (поиск в повернутом массиве)
Наивно: Линейный поиск
Оптимально: Модифицированный бинарный поиск

🔸Count Inversions (подсчёт инверсий)
Наивно: Вложенные циклы, O(n²)
Оптимально: Модифицированный Merge Sort, O(n log n)

🔸Check if Tree is Balanced (проверка сбалансированности дерева)
Наивно: Пересчитывать высоту на каждом шаге
Оптимально: Один проход — возвращаем высоту и статус баланса

🔸Merge k Sorted Lists (слияние k отсортированных списков)
Наивно: Объединить всё и отсортировать
Оптимально: Слияние k списков через Min Heap, O(N log k)

🔸Longest Consecutive Sequence (длиннейшая последовательность чисел)
Наивно: Сортировка и проход
Оптимально: HashSet + сканирование, O(n)

🔸Word Ladder (преобразование слов)
Наивно: BFS от каждого слова
Оптимально: Предобработка + двусторонний BFS

🔸Number of Islands (количество островов)
Наивно: DFS без отметок
Оптимально: DFS/BFS/Union-Find с отслеживанием посещённых клеток

👉 Java Portal