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

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Для решения используем минимальную кучу, то есть PriorityQueue, в которой хранятся только k самых больших чисел. Самое маленькое из них — это как раз k-й по величине элемент

🟦При добавлении нового числа используем метод add:
➖если в куче меньше k элементов — число просто добавляется

➖если уже есть k элементов, то новое число сравнивается с наименьшим в куче:
▫если оно больше, то старое удаляется и добавляется новое, иначе шаг просто пропускается
▫так мы всегда поддерживаем только k самых больших чисел из всех, которые встречались

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

👩‍💻 Java Algo | #solution703

🟢Easy
3318. Find X-Sum of All K-Long Subarrays I

Company: 🔍

📝Дан целочисленный массив nums и два целых числа k и x. Верните массив answer длины n - k + 1, где answer[i] — X-сумма подмассива nums[i..i + k - 1].

X-сумма вычисляется следующим образом:
➖посчитайте частоту всех элементов в подмассиве
➖вычислите сумму только x самых частых элементов. Если два элемента имеют одинаковую частоту, элемент с большим значением считается более частым

При этом, если подмассив содержит менее x различных элементов, его X-сумма равна сумме подмассива

💡: настройте компаратор очереди на сравнение частот элементов из HashMap

#leetcode3318 | #easy #priorityqueue

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

Time: O((n - k) * klogk)
Space: O(n)

💡 Идея
🟦Проходим по массиву окном длины k и для каждого определяем частоты всех чисел с помощью HashMap

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

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

🟦В итоге формируется массив, содержащий такие суммы для всех возможных окон длины k в исходном массиве

👩‍💻 Java Algo | #solution3318

🟡Medium
253. Meeting Rooms II

Company: 📱📱🏢

📝Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимально необходимое количество переговорных комнат

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

#leetcode253 | #medium #priorityqueue

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

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

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

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

🟦Если текущая встреча начинается после завершения самой ранней встречи (pq.peek()), значит, комната освобождается, и можно снова её использовать, а время окончания этой встречи из очереди удалить

🟦В результате размер очереди указывает на максимальное количество одновременно активных встреч, что и есть минимально необходимое число переговорных комнат

👩‍💻 Java Algo | #solution253

🟡Medium
2182. Construct String With Repeat Limit

Company: 🔍 📱

📝Вам дана строка s и целое число repeatLimit.

Постройте новую строку, используя символы из s так, чтобы ни одна буква не встречалась подряд более repeatLimit раз, при этом необязательно использовать все символы.

Верните лексикографически наибольшую возможную строку

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

#leetcode2182 | #medium #priorityqueue

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

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Сначала посчитаем частоту каждого символа с помощью HashMap и поместим все уникальные в PriorityQueue, которая упорядочена по убыванию для построения строки в лексикографически наибольшем порядке

🟦Затем запускаем процесс формирования строки:
➖извлекаем из очереди наибольший доступный символ и добавляем его к результату не более repeatLimit раз

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

➖если оба символа ещё встречаются — возвращаем их обратно в очередь

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

👩‍💻 Java Algo | #solution2182

🟡Medium
1642. Furthest Building You Can Reach

Company: 📱📱🏢

📝Дан массив heights — высоты зданий и числа bricks и ladders — количество кирпичей и лестниц.

Вы начинаете с 0-го здания и движетесь вправо:

▫если следующее здание не выше текущего — просто спрыгиваете
▫если выше — используйте кирпичи на разницу высот или лестницу, которая покрывает любую высоту

Верните индекс самого дальнего здания, до которого можно добраться при оптимальном использовании ресурсов

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

#leetcode1642 | #medium #priorityqueue

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

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Проходим по массиву и на каждом шаге:
➖оцениваем разницу в высоте между следующим зданием и текущим — climb

➖если climb > 0, значит нужно каким-то образом преодолеть подъём, для чего всегда используем лестницы и добавляем текущий подъем в PriorityQueue

➖но, если размер очереди стал больше ladders, значит лестницы закончились, и пора использовать кирпичи вместо самого маленького подъема, который мы достаем из очереди

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

🟦В результате получаем оптимальное использование ресурсов, жадно используя лестницы для самых больших подъемов, а кирпичи — для меньших

👩‍💻 Java Algo | #solution1642

🟡Medium
1353. Maximum Number of Events That Can Be Attended

Company: 💰🚖🏢

📝Дан массив events, где events[i] = [startDayi, endDayi] — мероприятие, которое начинается в день startDayi и заканчивается в endDayi.

Вы можете посетить мероприятие i в любой день d, который входит в интервал его проведения.

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

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

#leetcode1353 | #medium #priorityqueue

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

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

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

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

➖затем все мероприятия, начинающиеся в этот день, добавляются в приоритетную очередь

➖далее из очереди достаем мероприятие с ближайшей датой окончания и увеличиваем результат

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

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

👩‍💻 Java Algo | #solution1353

🟡Medium
373. Find K Pairs with Smallest Sums

Company: 🔍📕📱

📝Даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.

Верните k пар с наименьшими суммами. Пара должна состоять из одного элемента из nums1 и одного элемента из nums2

💡: сформируйте начальные пары nums1[i] + nums2[0] для всех i и постепенно расширяйте их, двигаясь по второму массиву, извлекая минимальные суммы из очереди

#leetcode373 | #medium #priorityqueue

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

Time: O(k log(n))
Space: O(n + k)

💡 Идея
🟦Если перебирать все возможные пары, мы получили бы сложность O(n²), поэтому воспользуемся тем фактом, что массивы отсортированы и будем генерировать только те пары, которые потенциально могут входить в k наименьших, складывая их в PriorityQueue в формате массива {sum, nums1_i, nums2_i}

🟦Сначала добавляем в очередь только пары, состоящие из каждого элемента nums1 и первого элемента nums2, таким образом формируя всех начальных кандидатов на минимальные пары

🟦В цикле, пока k > 0:
➖извлекаем пару с наименьшей суммой и добавляем в результат

➖добавляем следующую пару с тем же элементом из nums1, но со следующим элементом из nums2:
▫если nums2[j] уже дал минимальную пару, то следующий кандидат — это nums2[j+1]

➖уменьшаем k

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

👩‍💻 Java Algo | #solution373

🟡Medium
1834. Single-Threaded CPU

Company: 🔍📱📱

📝Дано n задач tasks, где tasks[i] = {enqueueTime_i, processingTime_i} — время поступления задачи enqueueTime и время ее обработки processingTime.

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

➖если ЦП простаивает и есть доступные задачи, он выберет задачу с наименьшим временем обработки. Если несколько задач имеют одинаковое наименьшее время обработки, он выберет задачу с наименьшим индексом
➖после запуска задачи ЦП будет обрабатывать ее всю без остановки
➖ЦП может завершить задачу, а затем мгновенно начать новую

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

Объяснение для примера 1:

- В момент времени = 1 задача 0 доступна для обработки. Доступные задачи = {0}.

- Также в момент времени = 1 простаивающий ЦП начинает обработку задачи 0. Доступные задачи = {}.

- В момент времени = 2 задача 1 доступна для обработки. Доступные задачи = {1}.

- В момент времени = 3 задача 2 доступна для обработки. Доступные задачи = {1, 2}.

- Также в момент времени = 3 ЦП завершает задачу 0 и начинает обработку задачи 2, так как она самая короткая. Доступные задачи = {1}.

- В момент времени = 4 задача 3 доступна для обработки. Доступные задачи = {1, 3}.

- В момент времени = 5 ЦП завершает задачу 2 и начинает обработку задачи 3, так как она самая короткая. Доступные задачи = {1}.

- В момент времени = 6 ЦП завершает задачу 3 и начинает обработку задачи 1. Доступные задачи = {}.

- В момент времени = 10 ЦП завершает задачу 1 и переходит в режим ожидания.

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

#leetcode1834 | #medium #priorityqueue

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

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

💡 Идея
🟦В начале создадим новый массив sorted, в который скопируем все задачи, добавляя к каждой её исходный индекс, а затем отсортируем его по времени поступления задачи

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

🟦Далее выполняем основной цикл, пока все задачи не будут обработаны или пока в очереди есть задачи:
➖если очередь пуста и текущий момент времени меньше времени поступления следующей задачи, «перематываем» время вперёд на момент поступления этой задачи

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

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

🟦Таким образом, алгоритм симулирует процесс выполнения задач, учитывая и поступление, и приоритет выполнения

👩‍💻 Java Algo | #solution1834

🔴Hard
632. Smallest Range Covering Elements from K Lists

Company: 📕🏢✴️

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

Диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c если b - a == d - c

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

#leetcode632 | #hard #priorityqueue

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

Time: O(n log(k))
Space: O(k)

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

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

➖затем обновляем текущий диапазон, если новый оказался уже

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

➖если есть — добавляем его в очередь и параллельно сравниваем с максимальным

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

👩‍💻 Java Algo | #solution632

🔴Hard
2402. Meeting Rooms III

Company: 📱🚖📕

📝Дано n комнат, пронумерованных от 0 до n - 1.

Вам дан массив meetings, где meetings[i] = [start_i, end_i) — время встречи в течение полузакрытого интервала. Все значения start уникальны.

Встречи распределяются по комнатам следующим образом:

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

Верните номер комнаты, в которой было больше всего встреч. Если ответов несколько, верните комнату с наименьшим номером

Объяснение для примеров:

Пример 1.
- В момент времени 0 обе комнаты не используются. Первая встреча начинается в комнате 0.
- В момент времени 1 не используется только комната 1. Вторая встреча начинается в комнате 1.
- В момент времени 2 используются обе комнаты. Третья встреча задерживается.
- В момент времени 3 используются обе комнаты. Четвертая встреча задерживается.
- В момент времени 5 заканчивается встреча в комнате 1. Третья встреча начинается в комнате 1 на период времени [5,10).
- В момент времени 10 заканчиваются встречи в обеих комнатах. Четвертая встреча начинается в комнате 0 на период времени [10,11).
В обеих комнатах 0 и 1 было проведено по 2 встречи, поэтому мы возвращаем 0.

Пример 2.
- В момент времени 1 все три комнаты не используются. Первая встреча начинается в комнате 0.
- В момент времени 2 комнаты 1 и 2 не используются. Вторая встреча начинается в комнате 1.
- В момент времени 3 не используется только комната 2. Третья встреча начинается в комнате 2.
- В момент времени 4 используются все три комнаты. Четвертая встреча задерживается.
- В момент времени 5 заканчивается встреча в комнате 2. Четвертая встреча начинается в комнате 2 на период времени [5,10).
- В момент времени 6 используются все три комнаты. Пятая встреча задерживается.
- В момент времени 10 заканчиваются встречи в комнатах 1 и 2. Пятая встреча начинается в комнате 1 на период времени [10,12).
В комнате 0 была проведена 1 встреча, а в комнатах 1 и 2 — по 2, поэтому мы возвращаем 1.

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

#leetcode2402 | #hard #priorityqueue

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

Time: O(m log(m))
Space: O(m + n)

💡 Идея
🟦Сначала сортируем meetings по времени начала, чтобы обрабатывать события в хронологическом порядке

🟦Далее используем две приоритетные очереди: free для хранения свободных комнат по их индексам и used для занятых комнат с информацией о времени освобождения и номере комнаты

🟦Проходим по всем встречам и для каждой:
➖сначала освобождаем комнаты, в которых встречи уже закончились: текущее время больше или равно времени окончания встречи в очереди used

➖если есть свободные комнаты, встреча назначается в первую свободную по индексу (free.peek())

➖если свободных комнат нет — время начала текущей встречи переносится на ближайшее время освобождения одной из комнат (used.peek())

➖в массиве freq подсчитываем частоту использования комнат, увеличивая счетчик по индексу комнаты

🟦После обработки всех встреч с помощью функции getMaxFreq проходим по массиву freq и находим комнату, которая использовалась чаще всего:

private int getMaxfreq(int[] freq) {
int max = 0;
int room = -1;

for (int i = 0; i < freq.length; i++) {
if (freq[i] > max) {
max = freq[i];
room = i;
}
}

return room;
}

👩‍💻 Java Algo | #solution2402

🔴Hard
295. Find Median from Data Stream

Company: 📕📱🚖

📝Реализуйте класс MedianFinder:

▫MedianFinder() инициализирует MedianFinder объект
▫void addNum(int num) добавляет целое число num из потока данных в структуру данных
▫double findMedian() возвращает медиану всех элементов на данный момент

Медиана — это среднее значение в упорядоченном целочисленном списке. Если размер списка четный, медиана — это среднее значение двух средних значений

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

#leetcode295 | #hard #priorityqueue

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

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

💡 Идея
🟦Для реализации используем две приоритетные очереди: left — содержащую левую половину чисел с приоритетом на большие значения, right — содержащую правую половину чисел с приоритетом на меньшие значения

🟦Благодаря такому разделению медиана всегда будет находиться либо на вершине одной из очередей, либо как среднее значение между вершинами двух очередей

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

🟦Медиану определяем в зависимости от размера очередей:
➖если обе кучи равны по размеру, медиана — это среднее значение двух центральных элементов (вершин очередей)
➖если одна очередь больше другой по размеру, медиана — это вершина большей очереди

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

👩‍💻 Java Algo | #solution295