🟢Easy
1539. Kth Missing Positive Number

Company: 🏢📱📱

📝Дан отсортированный массив arr натуральных чисел и целое число k.

Верните k-ое пропущенное число в этом массиве

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

#leetcode1539 | #easy #binarysearch

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

Time: O(logn)
Space: O(1)

💡 Идея
🟦Чтобы применить бинарный поиск, нужно уметь быстро определять сколько положительных чисел отсутствует перед i-м элементом массива

🟦Для этого сравним входной массив [2, 3, 4, 7, 11] с массивом без отсутствующих чисел: [1, 2, 3, 4, 5]. Количество отсутствующих целых чисел — это простая разница между соответствующими элементами этих двух массивов:
➖Перед 2 отсутствует: 2 - 1 = 1
➖Перед 7 отсутствует: 7 - 4 = 3
➖Перед 11 отсутствует: 11 - 5 = 6

То есть, получаем формулу: arr[i] – (i + 1)

🟦Теперь применяем бинарный поиск — ищем первую позицию, где пропущено k или больше чисел:
➖если количество отсутствующих чисел перед arr[mid] меньше k — продолжаем поиск в правой части массива: l = mid + 1

➖иначе случае продолжаем поиск на левой стороне: r = mid - 1

🟦После цикла получаем, что l = r + 1. Это означает, что на позиции r пропущено меньше, чем k чисел, а на l позиции — k или больше. То есть, k-е пропущенное число находится между arr[r] и arr[l]

🟦Количество целых чисел, пропущенных до arr[r]: missed = arr[r] - (r + 1), значит k- е число равно: arr[r] + (k - missed).
В итоге получаем такой ответ: arr[r] + k - (arr[r] - r - 1) = k + r + 1 = k + l

👩‍💻 Java Algo | #solution1539

🟡Medium
540. Single Element in a Sorted Array

Company: 🔍📱✴️

📝Дан отсортированный массив, состоящий из целых чисел, где каждый элемент встречается ровно дважды, за исключением одного элемента, который встречается ровно один раз.

Верните элемент, который встречается только один раз. Реализуйте решение за O(logn) по времени и O(1) по памяти

💡: используйте тот факт, что длина массива всегда нечетная

#leetcode540 | #medium #binarysearch

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

Time: O(logn)
Space: O(1)

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

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

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

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

👩‍💻 Java Algo | #solution540

🟡Medium
2560. House Robber IV

Company: 🚔📱📱

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

Способность грабителя — это максимальная сумма, которую он способен украсть из одного дома.

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

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

#leetcode2560 | #medium #binarysearch

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

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

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

🟦Для этого выставляем левую границу l, как минимальное значение массива, а правую r, как максимальное

🟦Далее выполняем процедуру поиска, пока l < r:
➖вычисляем mid, а затем сразу проверяем полученную способность, проходя по массиву и увеличивая счетчик, если текущий элемент <= mid

➖если получили count >= k, значит можно попробовать уменьшить способность, сдвинув правый указатель: r = mid

➖иначе нам не хватает текущей способности и необходимо искать ее правее: l = mid + 1

🟦После поиска получаем в l ответ на задачу

👩‍💻 Java Algo | #solution2560

🟡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