🔴Hard
410. Split Array Largest Sum

Company: 📱🚔📱

📝Дан массив целых чисел nums и целое число k, разделите nums на k непустых подмассивов таким образом, чтобы наибольшая сумма любого подмассива была минимальной.

Верните минимальную наибольшую сумму разделения

💡: ищите минимальную сумму в диапазоне [max(nums), sum(nums)], при которой nums можно разбить на k подмассивов с суммой не больше этой величины

#leetcode410 | #hard #binarysearch

✅ Решение задачи 410

Time: O(nlog(s))
Space: O(1)

💡 Идея
🟦Для начала можно посмотреть, а какие вообще могут быть значения:
➖минимально возможная сумма — подмассив, состоящий только из одного максимального элемента, потому что он обязательно должен попасть в какую-то часть
➖максимально возможная сумма — сумма всего массива

🟦Итого мы получили диапазон, для которого можно применить бинарный поиск. Теперь после вычисления mid, отвечаем на вопрос: "Можно ли разделить массива на k частей, чтобы сумма в каждой не превышала mid?"

🟦Для этого проходим по массиву и простым жадным алгоритмом суммируем элементы в текущую сумму, если она превысила mid, значит пора начать новую часть массива и сбросить текущую сумму на текущий элемент

🟦Затем проверяем сколько частей получили:
➖если больше k, значит предполагаемая сумма mid слишком маленькая и необходимо ее увеличить: l = mid + 1
➖если k или меньше, значит мы нашли подходящую сумму, но можно попытаться ее уменьшить: r = mid – 1. При этом, если получили меньше k частей — это не проблема, так как можно дополнительно разделить любую часть

🟦После завершения бинарного поиска в l окажется наименьшая возможная максимальная сумма подмассива, при которой можно разбить массив на k частей

👩‍💻 Java Algo | #solution410

🔴Hard
1231. Divide Chocolate

Company: 🔍

📝У вас есть плитка шоколада, представленная массивом sweetness, где каждый элемент — это уровень сладости одного кусочка.

Вы хотите поделить шоколад на k + 1 частей, разрезав плитку k раз, при этом вы забираете себе наименее сладкий из полученных кусков. Ваша цель — максимизировать сладость этой наименьшей части, которую вы себе оставите.

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

💡: проверяйте, можно ли разбить массив так, чтобы каждая из k + 1 частей была хотя бы сладости mid из диапазона поиска [min(a), sum(a)]

#leetcode1231 | #hard #binarysearch

✅ Решение задачи 1231

Time: O(nlog(s))
Space: O(1)

💡 Идея
🟦Начинаем бинарный поиск в диапазоне от минимальной сладости одного куска до суммы всей шоколадки, так как это и есть границы возможного ответа

🟦После вычисления mid, как предполагаемой минимальной сладости, проверяем, возможно ли разделить массив на k + 1 частей, каждая из которых имеет суммарную сладость не меньше mid

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

🟦После прохода по массиву проверяем:
➖если count >= k + 1, значит можно разделить массив с такой минимальной сладостью — сохраняем результат и пробуем его улучшить: l = mid + 1

➖иначе — частей недостаточно, пробуем уменьшить mid, так как требуемая сладость слишком высока: r = mid – 1

🟦Такой подход позволяет найти максимально возможную минимальную сладость, при которой можно разделить шоколад на k + 1 частей

👩‍💻 Java Algo | #solution1231

🔴Hard
4. Median of Two Sorted Arrays

Company: 📱📱🔴

📝Даны два отсортированных массива nums1 и nums2 размером m и n соответственно, объедините их в один отсортированный массив и верните его медиану.

Напишите алгоритм со временем работы не хуже O(log (m+n))

💡: используя бинарный поиск по одному массиву, найдите такое количество элементов из него, которое вместе с дополняющим количеством из второго массива правильно формирует левую половину объединенных массивов

#leetcode4 | #hard #binarysearch

✅ Решение задачи 4

Time: O(log(min(n,m)))
Space: O(1)

💡 Идея
🟦Если соединить два массива и отсортировать, как можно понять, что элемент является медианой?
Очевидно, все элементы перед медианой — меньше или равны, все элементы после — больше или равны

🟦Попробуем найти левую половину, то есть начальный отрезок объединённого массива:

Если мы вычислим mid1 — количество элементов из первого массива, попадающих в левую половину, то тем самым определим границу между левой и правой частями в первом массиве. Конец левой части будет элемент nums1[mid1 - 1], начало правой — nums1[mid1]

🟦Как тогда получить аналогичную границу во втором массиве?

На самом деле, нам не нужно искать её бинарным поиском. Мы уже знаем, сколько всего элементов должно быть в левой половине — half. А значит, если мы взяли mid1 из первого массива, то из второго остаётся взять mid2 = half - mid1. Это и будет количество элементов из второго массива в левой части

🟦Далее — основная проверка на корректность разбиения:
➖если конец левой части первого массива ≤ начало правой части второго, и одновременно конец левой части второго массива ≤ начало правой части первого, то объединённая левая часть будет отсортированной, и, следовательно, такое разбиение — правильное

🟦Что дальше?
➖если общая длина массивов нечётная, то медианой будет максимум из двух концов левой части
➖если чётная — медиана будет равна среднему между максимумом из левых концов и минимумом из правых начал

🟦В случае, когда проверка не прошла:
➖если конец левой части первого массива больше начала правой части второго, значит мы взяли слишком много элементов из первого массива — надо сдвинуться влево: r = mid1 - 1
➖если наоборот — двигаемся вправо: l = mid1 + 1

🟦Ответы на возможные вопросы

▫Почему r = n1, а не n1 – 1?
Потому что мы ведём бинарный поиск не по индексам, а по количеству элементов, которые нужно взять из первого массива в левую часть объединённого массива

▫Почему half = (n1 + n2 + 1) /2, а не (n1 + n2) / 2?
Это делается для корректного определения количества элементов в левой половине в случае, когда общее количество элементов нечётное

▫Зачем в начале условие if (nums1.length > nums2.length)...?
Данное условие используется для обработки случая, когда один из массивов пустой, а также предотвращает отрицательные значения mid2 и гарантирует, что бинарный поиск будет выполняться по меньшему массиву, что делает алгоритм устойчивым и эффективным

👩‍💻 Java Algo | #solution4

🖼Иллюстрация алгоритма к задаче 4

Пример: nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5,6,7]

#figure #binarysearch

➡️ Стартуем тему бинарного дерева

▫Binary Tree — это структура данных, где каждый узел имеет не более двух потомков: левого и правого.

Бинарные деревья широко используются для хранения, обработки и обхода данных, таких как выражения, файловые системы или структура HTML-страниц. Например: дерево принятия решений в игре (если "нет" — налево, если "да" — направо).

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

▫Binary Search Tree (BST) — бинарное дерево поиска, частный случай бинарного дерева, в котором:
➖все значения в левом поддереве меньше значения текущего узла
➖все значения в правом поддереве больше
Такое упорядочивание позволяет быстро искать, добавлять и удалять значения.

▫Основные алгоритмы обхода: BFS и DFS
🔹BFS (Breadth-First Search) — обход в ширину:
➖ проходит по дереву уровень за уровнем: сначала корень, затем все его дети, потом внуки и так далее
➖ работает с помощью очереди (queue) — узлы обрабатываются в порядке поступления
➖ пример: поиск ближайшего выхода из лабиринта — сначала проверяешь все соседние комнаты, потом комнаты за ними, постепенно расширяя круг

🔹 DFS (Depth-First Search) — обход в глубину:
➖ проходит по дереву, уходя как можно глубже по одной ветке, затем возвращается
➖реализуется через рекурсию или стек (stack) — сначала погружается, потом возвращается
➖ пример: исследование пещеры — идёшь до конца одного тоннеля, только потом возвращаешься и пробуешь следующий путь

#binarytree

📚 Про рекурсию

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

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

▫Представь, что ты надел несколько пар носков один на другой и хочешь их снять:
➖сначала ты снимаешь верхнюю пару, потом — ещё одну, и так далее, пока не останешься босиком.
Ты повторяешь одно и то же действие, уменьшая оставшийся объём работы. При этом обязательно должно быть условие остановки, иначе будешь снимать носки вечно 😄.

▫Ближе к коду: как работает рекурсия внутри программы, как компьютер "запоминает" каждый шаг и потом возвращается назад?

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

▫Классический пример — вычисление факториала. Каждый вызов ждёт результат следующего и только потом считает своё значение:

public static int factorial(int n) {
    if (n == 1) return 1;             // базовый случай
    return n * factorial(n - 1);      // рекурсивный шаг
}

factorial(3)
→ 3 * factorial(2)
→ 3 * (2 * factorial(1))
→ 3 * (2 * 1) = 6

#recursion

🟢Easy
101. Symmetric Tree

Company: 📕🔍📱

📝Дано двоичное дерево.

Верните true, если оно является зеркальным отражением самого себя, то есть симметричным относительно своего центра

💡: рекурсивно проверяйте каждый узел, сравнивая поддеревья с противоположных сторон

#leetcode101 | #easy #binarytree

✅ Решение задачи 101

Time: O(n)
Space: O(n)

💡 Идея
🟦Чтобы понять идею симметрии в бинарном дереве, достаточно взглянуть на его структуру: каждый правый узел на одной стороне должен соответствовать левому узлу на другой стороне — и наоборот

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

🟦Создадим вспомогательную функцию helper, принимающую два узла. Сначала обрабатываем базовые случаи:
➖если оба узла равны null, значит, мы достигли конца поддеревьев синхронно — возвращаем true
➖если только один из узлов равен null, симметрия нарушена — возвращаем false
➖если значения в узлах не совпадают — также возвращаем false

🟦Если все эти проверки пройдены, рекурсивно вызываем helper для левого поддерева первого узла и правого поддерева второго, а также для правого поддерева первого и левого поддерева второго — тем самым продолжая зеркальное сравнение

👩‍💻 Java Algo | #solution101

🟢Easy
404. Sum of Left Leaves

Company: 🚔📱❤️

📝Дано двоичного дерево, вернуть сумму всех левых листьев.

Лист — это узел без потомков. Левый лист — это лист, который является левым потомком другого узла

💡: в рекурсивную функцию добавьте "флаг" левого узла

#leetcode404 | #easy #binarytree

✅ Решение задачи 404

Time: O(n)
Space: O(h)

💡 Идея
🟦Решение основано на рекурсивном обходе дерева (DFS) с передачей дополнительного логического флага isLeft, который указывает, является ли текущий узел левым ребёнком своего родителя. Это позволяет точно определить, какие листья левые и включать в сумму только их

🟦Реализуем вспомогательную функцию dfs:
➖Базовый случай — если узел null, возвращаем 0

➖Если узел — лист (нет потомков):
▫если он левый (isLeft == true), возвращаем его значение
▫иначе возвращаем 0

➖Если узел — не лист:
▫рекурсивно вызываем dfs для левого поддерева с флагом true
▫для правого поддерева — с флагом false
▫возвращаем сумму результатов обоих вызовов

👩‍💻 Java Algo | #solution404

🟢Easy
270. Closest Binary Search Tree Value

Company: 🏢📱📱

📝Дано двоичное дерево поиска (BST) и значение target.

Верните значение в BST, которое ближе всего к target. Если есть несколько ответов, верните наименьший

💡: пользуясь свойством BST, найдите для target ближайшие границы сверху и снизу

#leetcode270 | #easy #binarytree

✅ Решение задачи 270

Time: O(h)
Space: O(1)

💡 Идея
🟦Главное свойство BST: в левом поддереве всегда лежат меньшие значения, в правом — большие

🟦Чтобы найти значение, ближайшее к target, будем искать две границы:
➖нижнюю (low) — наибольшее значение, не превышающее target
➖верхнюю (high) — наименьшее значение, не меньшее target

🟦Пока текущий узел не равен null, сравниваем его значение с target:
➖если значение меньше target, это возможный кандидат на low, но потенциально ближе значение может быть правее
➖если значение больше или равно, это кандидат на high, но есть шанс найти более близкое значение левее

🟦Так мы обходим BST, не перебирая все узлы, а двигаясь по направлению к потенциально лучшим вариантам и запоминая текущие приближения. В конце сравниваем low и high и возвращаем то, что ближе к target

👩‍💻 Java Algo | #solution270

🟡Medium
863. All Nodes Distance K in Binary Tree

Company: 📱🚖✴️

📝Дан корень двоичного дерева, целевой узел target и целое число k.

Верните список значений всех узлов (в любом порядке), которые находятся на расстоянии k от целевого узла

💡: сохраните в HashMap ссылки на родителей для всех узлов, а затем начните обход дерева с целевого узла со счетчиком k

#leetcode863 | #medium #binarytree

✅ Решение задачи 863

Time: O(n)
Space: O(n)

💡 Идея
🟦В данной задаче легко определить узлы, находящиеся на расстоянии k от target в пределах одного поддерева (просто запускаем dfs от узла target cо счетчиком). Сложность состоит в том, чтобы найти подходящие узлы, которые находятся в других частях дерева (как 5 и 1 в примере)

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

🟦Далее остается запустить dfs от узла target, но кроме обычных направлений к потомкам (влево и вправо), добавляем движение наверх (к родителю). На каждом шаге глубина k уменьшается, и при достижении k == 0 текущий узел добавляется в результат. Для предотвращения зацикливания используем HashSet, куда добавляем уже обработанные узлы

🟦Таким образом:
➖построение связей с родителями выполняется за O(n)
➖dfs также посещает каждый узел не более одного раза — O(n)
В итоге получаем эффективный алгоритм за O(n)

👩‍💻 Java Algo | #solution863

🟡Medium
314. Binary Tree Vertical Order Traversal

Company: 🏢🔍📱

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

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

💡: используйте обход в ширину и группируйте узлы по столбцам в HashMap

#leetcode314 | #medium #binarytree

✅ Решение задачи 314

Time: O(n)
Space: O(n)

💡 Идея
🟦Назначим корню столбец с номером 0 и теперь, двигаясь влево, уменьшаем столбец на 1, вправо – увеличиваем на 1, получая для каждого узла уникальный номер столбца. Все значения узлов группируем в HashMap, где ключ — это номер столбца, а значение — список узлов, находящихся в этом столбце

🟦Для обхода дерева используем не привычный dfs, а обход в ширину (bfs), который позволяет обрабатывать узлы уровень за уровнем, гарантируя правильный порядок сверху вниз:

В реализации bfs используем очередь Queue<Pair>, где Pair — это структура, содержащая сам узел и его номер столбца. Каждый раз, когда мы извлекаем узел из очереди, мы добавляем его значение в список соответствующего столбца в HashMap и помещаем в очередь его левого и правого детей с обновлёнными номерами столбцов.

private static class Pair {
TreeNode node;
int column;

public Pair(TreeNode node, int column) {
this.node = node;
this.column = column;
}
}

🟦После завершения обхода, HashMap содержит все значения, отсортированные по вертикальным столбцам, но правильный порядок самих столбцов не гарантирован, поэтому во время обхода отслеживаем минимальный и максимальный номер столбца (minCol и maxCol).
Это позволяет в конце пройти по столбцам от самого левого до самого правого, добавляя значения из HashMap в итоговый список в нужном порядке

👩‍💻 Java Algo | #solution314

🟡Medium
99. Recover Binary Search Tree

Company: 🔍📱📱

📝Дано двоичное дерево поиска (BST), где значения ровно двух узлов были поменяны местами по ошибке.

Восстановите дерево, вернув узлам правильные значения

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

#leetcode99 | #medium #binarytree

✅ Решение задачи 99

Time: O(n)
Space: O(n)

💡 Идея
🟦Для начала взглянем на массив [1,5,3,4,2], в котором только два элемента (2, 5) стоят не на своих местах для полностью отсортированного

🟦У данных элементов есть признак – они меньше предыдущего значения, поэтому можно использовать это свойство для поиска неверных узлов в BST, остается только правильно пройти по дереву

🟦Для этого выполняем in-order обход:
➖идём всегда к самому левому (наименьшему) узлу, по пути сохраняя узлы в стек, чтобы потом вернуться к ним

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

▫если это первое нарушение, мы сохраняем предыдущий узел как first, а текущий — как second
▫если first уже найден, то это второе нарушение, и мы обновляем только second

➖после обработки текущего узла переходим в его правое поддерево и продолжаем обход

🟦Когда весь обход завершён, достаточно поменять значения узлов first и second, чтобы восстановить правильный порядок в BST

👩‍💻 Java Algo | #solution99