🔴Hard
23. Merge k Sorted Lists

Company: 🏢📱❤️

📝Вам дан массив k связанных списков lists, где каждый отсортирован в порядке возрастания.

Объедините все списки в один отсортированный и верните его

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

#leetcode23 | #hard #linkedlist

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

Time: O(nlogk)
Space: O(1)

💡 Идея
🟦Одним из простых решений могло стать последовательное слияние всех списков с первым, но тогда бы мы получили сложность по времени O(nk), что не так хорошо

🟦Вместо этого можно соединять все списки парами с шагом step, пока данный шаг меньше длины массива

🟦В начале step равен 1, то есть мы соединяем только текущий и следующий список: merge(list[i], list[i + step]), но далее — после каждого прохода по массиву, мы увеличиваем его в два раза, чтобы объединять уже более длинные промежуточные списки

🟦При этом шаг i прохода по массиву должен быть в два раза больше step, чтобы “переступать” через уже объединенные списки, не затрагивая их повторно

🟦Таким образом, массив списков делится и объединяется по парам logk раз и в итоге мы получаем сложность O(nlogk)

👩‍💻 Java Algo | #solution23

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

#figure #linkedlist

🔴Hard
25. Reverse Nodes in k-Group

Company: 🔍🅰️🚀

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

Если число узлов не кратно k, то оставшиеся узлы оставьте в том же порядке

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

#leetcode25 | #hard #linkedlist

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

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

💡 Идея
🟦В основе решения — вспомогательная функция getKNode, которая возвращает k-й узел от начала текущей группы. Если такой узел существует, значит группа полная и её можно перевернуть знакомым алгоритмом

🟦Перед разворотом сохраняем начало следующей группы: kNode.next и используем его как начальное значение для prev, чтобы сразу соединить текущую группу с оставшейся частью списка

🟦После разворота соединяем предыдущую часть списка с новой головой группы: prevPart.next = kNode, затем сдвигаем prevPart к концу текущей уже перевёрнутой группы

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

👩‍💻 Java Algo | #solution25

➡️ Стартуем тему бинарного поиска

Представь, что кто-то загадал число от 1 до 100, и ты пытаешься его угадать, задавая вопросы: "твоё число больше этого?" или "меньше?".

Самый быстрый способ это сделать — каждый раз отбрасывать половину возможных вариантов. Для этого нужно начать с середины диапазона — с числа 50.

Спрашиваешь: "Твоё число больше 50?":
▫Если да — значит, всё, что меньше или равно 50, можно забыть. Теперь ты ищешь только в диапазоне от 51 до 100.
▫Если нет — значит, загаданное число находится где-то между 1 и 49.

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

Это и есть бинарный поиск — на каждом шаге ты делишь оставшийся диапазон пополам и выбираешь нужную половину в зависимости от условия. Важно помнить, что такой подход работает только с отсортированными данными, без этого алгоритм не сможет правильно сузить область поиска.

Пример кода бинарного поиска заданного числа target в массиве (задача):

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return -1;
    }
}

📎Обратите внимание, что для вычисления mid используется l + (r - l) / 2, вместо привычного (l + r) / 2. Это нужно для того, чтобы избежать переполнения int при больших значениях l и r.

#binarysearch

🟢Easy
35. Search Insert Position

Company: 📱🏢🚖

📝Дан отсортированный массив различных целых чисел и значение target. Верните индекс вставки target в массив.

Вам необходимо написать алгоритм со сложностью O(logn) по времени

💡: определите какой указатель бинарного поиска будет указывать на нужную позицию после цикла

#leetcode35 | #easy #binarysearch

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

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

💡 Идея
🟦Назначаем границы начального диапазона: l = 0, r = nums.length – 1

🟦Начинаем поиск, пока границы находятся в правильном отношении: l <= r:
➖находим середину: mid = l + (r - l) / 2

➖сравниваем nums[mid] с target:
▫если nums[mid] < target: значит target должен быть правее, поэтому сдвигаем левую границу: l = mid + 1
▫иначе target должен быть на этой позиции или левее, значит: r = mid – 1

🟦когда цикл завершён, l указывает на позицию вставки:
➖если target есть в массиве — это будет индекс его вхождения
➖если нет — это место, куда его нужно вставить, чтобы массив остался отсортированным

👩‍💻 Java Algo | #solution35

🟢Easy
69. Sqrt(x)

Company: 📱📱📱

📝Дано неотрицательное целое число x, вернуть квадратный корень x, округленного вниз до ближайшего целого числа.

Не допускается использование встроенных функций

💡: ищите ответ в диапазоне от 2 до x / 2

#leetcode69 | #easy #binarysearch

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

Time: O(logx)
Space: O(1)

💡 Идея
🟦Если x равен 0 или 1, сразу возвращаем его, так как корень равен самому числу

🟦Установим начальные границы для бинарного поиска: l = 2, r = x / 2, так как квадратный корень числа x точно не больше x / 2 (если x > 1)

🟦Начинаем поиск, пока l <= r:
➖находим среднее значение между l и r и его квадрат: square = (long) mid * mid, используя приведение к long, чтобы избежать переполнения

➖если square == x, найден точный корень — сразу возвращаем mid
➖если square < x, ищем большее значение, сдвигая левую границу: l = mid + 1
➖если square > x, ищем меньшее значение, сдвигая правую границу: r = mid - 1

🟦После завершения поиска, l будет указывать на первое число, квадрат которого превышает x, поэтому нужный результат — l - 1, то есть нужный по условию округлённый вниз квадратный корень

👩‍💻 Java Algo | #solution

🟢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