🟡Medium
2226. Maximum Candies Allocated to K Children

Company: 🚔🔍📱

📝Дан массив candies, где каждый элемент — это количество конфет в одной куче. Каждую кучу можно делить на любые части, но объединять кучи нельзя.

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

Верните максимальное количество конфет, которое может получить каждый ребенок

💡: ищите максимальную кучу в диапазоне [1, max(a)] и для каждой проверяйте, возможно ли собрать k таких куч

#leetcode2226 | #medium #binarysearch

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

Time: O(nlogm)
Space: O(1)

💡 Идея

🟦Вместо того чтобы пытаться "оптимально" делить кучи, предположим, что мы будем раздавать по x конфет каждому ребёнку. Теперь главный вопрос – это “Можно ли выдать x конфет k детям?”. Чтобы это проверить, достаточно пройти по исходному массиву и брать максимальное количество порций по x из каждой кучи, а затем сравнить их общее количество c k

🟦Чтобы не перебирать каждое значение x, воспользуемся бинарным поиском с границами: l — 1 самая маленькая порция и r — максимальное значение candies:

➖вычисляем mid и сразу считаем сколько детей можно обеспечить данной порцией: проходим по массиву и добавляем в count максимальное количество порций по mid для каждой кучи

➖если получили count >= k, значит можно сохранить ответ и попытаться увеличить размер порции: l = mid + 1

➖иначе порция слишком большая и необходимо ее уменьшить: r = mid – 1

🟦После цикла получаем в res максимальную порцию, которую можно выдать каждому из k детей

👩‍💻 Java Algo | #solution2226

🟡Medium
2300. Successful Pairs of Spells and Potions

Company: 🚔📱

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

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

Верните целочисленный массив answer, где answer[i] — количество зелий, которые составят успешную пару с заклинанием spells[i]

💡: для каждого заклинания ищите наименьшую силу зелья

#leetcode2300 | #medium #binarysearch

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

Time: O(nlogm)
Space: O(1)

💡 Идея
🟦Можно заметить, что при отсортированном массиве potions, если для spells[i] и potions[j] выполняется условие spells[i] * potions[j] >= success, то и для всех последующих potions оно также выполняется

🟦Поэтому бинарным поиском будем искать первую позицию в potions, для которой выполняется данное условие с текущим spells

🟦Для этого создаем отдельную функцию, в нее передаем текущее значение заклинания spells[i] и применяем бинарный поиск:

➖если potions[mid] * spell >= success, значит возможен более ранний подходящий элемент, сдвигаем правую границу: r = mid – 1
➖иначе ищем правее: l = mid + 1

🟦После завершения поиска — l указывает на первую подходящую позицию и количество успешных пар для текущего заклинания вычисляется, как potions.length - l. Повторяя это для каждого элемента из spells, мы формируем итоговый массив с ответами

👩‍💻 Java Algo | #solution2300

🟡Medium
1901. Find a Peak Element II

Company: 🚔📱🏢

📝Дана матрица m x n, в которой нет двух одинаковых соседних ячеек. Необходимо найти любой пиковый элемент и вернуть его координаты, как массив длины 2.

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

Вам необходимо написать алгоритм, который будет работать за время O(m log(n)) или O(n log(m))

💡: ищите максимум в столбце mid, а затем проверяйте не является ли этот элемент пиком, если нет — передвиньте соответствующий указатель в сторону большего соседа

#leetcode1901 | #medium #binarysearch

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

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

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

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

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

1⃣ Устанавливаем границы l и r по краям матрицы: на первый и последний столбец
2⃣Запускаем цикл, пока l <= r:
➖вычисляем средний столбец mid и для него находим строку с максимальным элементом

➖сравниваем максимум с горизонтальными соседями:
▫если он больше левого и правого — возвращаем найденный пик
▫если левый больше: r = mid - 1
▫если правый больше: l = mid + 1

🟦Наглядный пример:

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

👩‍💻 Java Algo | #solution1901

🟡Medium
81. Search in Rotated Sorted Array II

Company: 🔍🏢📱

📝Дан отсортированный по неубыванию массив nums, который был повернут на неизвестное число позиций, при этом массив может содержать повторяющиеся элементы. Также дано целое число target.

Вернуть true, если target находится в nums

💡: с помощью mid и l определяйте отсортированную часть массива, при этом исключайте nums[l] == nums[mid]

#leetcode81 | #medium #binarysearch

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

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

💡 Идея

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

🟦Вычисляем mid и сравниваем его с target, если совпадают – возвращаем true

🟦Далее делаем проверку: если nums[mid] == nums[l], тогда не удастся точно определить, отсортирована левая или правая часть массива, поэтому сдвигаем l вперед и пропускаем этот шаг цикла. При этом nums[l] точно не равен target, так как мы вернули бы true раньше, поэтому можно смело исключать данный элемент из рассмотрения

🟦Если nums[l] < nums[mid], значит левая часть массива (от l до mid) отсортирована, тогда проверяем, лежит ли target в этом диапазоне:
➖если да — продолжаем поиск слева: r = mid - 1
➖если нет — идём вправо: l = mid + 1

🟦Если nums[l] > nums[mid], значит правая часть (от mid до r) отсортирована, поступаем аналогично

🟦В результате каждый раз мы выбираем сторону поиска и избавляемся от дубликатов, при этом сохраняем эффективное решение. В среднем алгоритм работает за O(log(n)), но в худшем случаем, если всё заполнено одинаковыми значениями — за O(n)

👩‍💻 Java Algo | #solution81

🔴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