🟡Medium
962. Maximum Width Ramp

📝Дан целочисленный массив, вернуть максимальную ширину рампы.

Рампа в целочисленном массиве nums — это пара (i, j), для которой i < j и nums[i] <= nums[j]. Ширина такой рампы равна j - i

💡: используйте монотонный стек

163/200
#leetcode962 | #medium

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

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

⚡️ Идея
▫проходим по массиву и формируем стек начальных индексов в порядке убывания значений под ними:
➖кладем в стек текущий индекс, только если он пуст или элемент массива под верхним индексом стека больше текущего элемента
▫после проходим с конца массива и удаляем элементы из стека, пока элемент под верхним индексом меньше или равен текущему элементу, одновременно считая максимальную ширину рампы
▫Таким образом, для каждого элемента массива, начиная с конца, проверяется максимально возможная ширина рампы с использованием сформированного стека

#solution962

🟡Medium
539. Minimum Time Difference

📝Дан список точек времени в 24-часовом формате «ЧЧ:ММ», вернуть минимальную разницу в минутах между любыми двумя точками

💡: используйте массив размером 24 * 60 для сортировки

164/200
#leetcode539 | #medium

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

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

⚡️ Идея
▫инициализируем массив размером 24 * 60 и проходим по каждой точке времени, переводя ее в общее количество минут и отмечая в массиве соответствующую ячейку как true
▫затем проходим по этому массиву и, если текущее значение true:
➖ сохраняем первый индекс, если он не сохранен
➖ считаем минимальную разницу, используя указатель на предыдущий индекс
➖ сохраняем текущий индекс в предыдущий и последний
▫В конце считаем разницу между первым и последним индексом и возвращаем минимальный ответ

#solution539

🟡Medium
916. Word Subsets

📝Вам даны два строковых массива words1 и words2. Верните лист всех универсальных строк в words1.

▫Строка A из words1 — универсальная, если каждая строка B из words2 является подмножеством строки A.
▫Строка B является подмножеством строки A, если каждая буква B встречается в A, включая кратность
▫Например, "eo" является подмножеством "google", но не является подмножеством "apple"

💡: сформируйте общее слово из words2, используя массив частот символов

165/200
#leetcode916 | #medium

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

Time: O(N + M)
Space: O(1)

⚡️ Идея
▫проходим по words2 и составляем общую строку, которая имеет максимальное количество каждой буквы каждого слова из words2:
➖для каждого слова формируем свой массив частот с помощью функции count, а затем перемещаем его в общий массив, выбирая максимум из текущих частот букв
▫далее проходим по words1 и для каждого слова также формируем массив частот символов, а затем сравниваем этот массив с полученным массивом общего слова из words2, используя функцию check:
➖функция проверяет, что для каждого символа из B найдется такое же или большее количество символов в A
▫если текущая строка из words1 прошла проверку — добавляем ее в результат

#solution916

🟢Easy
408. Valid Word Abbreviation

📝Дана строка word и аббревиатура abbr, вернуть true, если строка соответствует заданной аббревиатуре

Строку можно сократить, заменив любое количество непустых подстрок их длинами, при этом длины не должны иметь начальных нулей. Например:

"substitution" -> "s10n"
"substitution" -> "sub4u4"
"substitution" -> "12"

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

166/200
#leetcode408 | #easy #premium

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

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

⚡️ Идея
▫проходим по строке word и аббревиатуре abbr с помощью двух указателей — i и j:
➖если текущий символ abbr цифра и не ноль — запускаем цикл с передвижением указателя j и записью всего числа, а затем передвигаем указатель i на соответствующее значение
➖если текущие символы равны, передвигаем оба указателя
➖иначе возвращаем false (символы не равны или число в abbr начинается с 0)
▫в конце возвращаем true, если оба указателя соответствуют длинам своих строк

#solution408

🟡Medium
2149. Rearrange Array Elements by Sign

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

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

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

167/200
#leetcode2149 | #medium

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

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

⚡️ Идея
▫инициализируем массив для ответа и два указателя — на положительные и отрицательные числа: pos = 0, neg = 1
▫далее проходим по массиву и сохраняем текущее число в массив, используя соответствующий указатель в зависимости от знака числа, а затем увеличиваем этот указатель на две позиции вперед
▫В результате получаем массив, который чередуется по знакам с сохранением исходного порядка

#solution2149

🟡Medium
2657. Find the Prefix Common Array of Two Arrays

📝 Даны два целочисленных массива A и B, вернуть их общий префиксный массив.

Общий префиксный массив A и B — это массив C, в котором C[i] равен количеству чисел, которые присутствуют в обоих массивах от 0 до i (включительно)

Для примера 2:

i = 0: ни одно число не является общим, поэтому C[0] = 0
i = 1: только 3 является общим для A и B, поэтому C[1] = 1
i = 2: 1, 2 и 3 являются общими A и B, поэтому C[2] = 3

💡: используйте HashSet

168/200
#leetcode2657 | #medium

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

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

⚡️ Идея
▫проходим по массивам и последовательно проверяем элементы A и B:
➖если в Set содержится текущий элемент массива, увеличиваем ячейку результата, а затем добавляем этот элемент в Set
▫после проверок суммируем текущую ячейку результата с предыдущей

#solution2657

🟢Easy
938. Range Sum of BST

📝Дано бинарное дерево поиска и два целых числа — low и high, вернуть сумму всех узлов со значениями в диапазоне [low, high]

💡: используйте свойство дерева

169/200
#leetcode938 | #easy

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

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

⚡️ Идея
▫так как в бинарном дереве поиска все элементы слева от текущего узла меньше, а справа больше — используем это свойство при обходе дерева с помощью вспомогательной функции:
➖суммируем к результату текущее значение, если оно находится в диапазоне
➖текущее значение > low — суммируем к результату рекурсивный вызов функции с левым поддеревом
➖текущее значение < high — суммируем к результату рекурсивный вызов функции с правым поддеревом
▫в результате, вызвав из основной функции вспомогательную с корнем дерева, получаем сумму всех узлов со значениями в заданном диапазоне

#solution938

🔴Hard
220. Contains Duplicate III

📝Вам дан массив целых чисел nums и два целых числа — indexDiff и valueDiff.

Найдите пару индексов (i, j), такую ​​что:

➖ i != j
➖ abs(i - j) <= indexDiff
➖ abs(nums[i] - nums[j]) <= valueDiff

Верните true, если такая пара существует

💡: используйте bucket sort, где bucket будет формироваться как [элемент массива / (valueDiff + 1)]

170/200
#leetcode220 | #hard

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

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

⚡️ Идея
▫для решения задачи используем bucket sort, где bucket будет формироваться как nums[i] / (valueDiff + 1) c округлением вниз, чтобы обработать отрицательные элементы

▫проблема, которую нужно решить — это проверка для элемента x наличия в текущем окне длиной indexDiff значения в диапазоне [x - valueDiff, x + valueDiff]

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

▫возвращаем true, если разность между элементом из bucket и текущим <= valueDiff или уже существует такой же bucket

▫добавляем (bucket, nums[i]) в HashMap и удаляем левый элемент из окна, если текущий индекс >= indexDiff

#solution220

🟡Medium
236. Lowest Common Ancestor of a Binary Tree

📝Дано бинарное дерево, найдите наименьшего общего предка для двух заданных узлов p и q (заданный узел также может являться предком)

💡: возвращайте некоторый флаг, если встретили p или q, обходя дерево в глубину

171/200
#leetcode236 | #medium

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

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

⚡️ Идея
▫реализуем функцию helper, которая проходит дерево в глубину и возвращает true, если поддерево содержит p или q

▫используем три переменные для отслеживания общего предка:
➖curr — отмечаем 1, если текущий узел равен p или q
➖left — отмечаем 1, если рекурсивный вызов функции для левого поддерева возвращает true
➖right — отмечаем 1, если рекурсивный вызов функции для правого поддерева возвращает true

▫если для текущего узла сумма трех переменных равна 2-м — значит мы нашли наименьшего общего предка

▫возвращаем true, если любая из трех переменных содержит p или q (их сумма больше 0)

#solution236

🟡Medium
275. H-Index II

📝Дан массив целых чисел citations, отсортированный по возрастанию, где citations[i] — количество цитирований, полученных исследователем для i-ой статьи.

Необходимо вернуть индекс Хирша исследователя с решением за O(logn) по времени

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

172/200
#leetcode275 | #medium

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

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

⚡️ Идея
▫реализуем бинарный поиск, в котором для перемещения указателей будем использовать на длину массива (n)

▫вычисляем mid, а затем сравниваем текущее значение цитирований с оставшимся количеством статей (n - mid) :
➖если цитирований больше — передвигаем правый указатель, пробуя увеличить индекс Хирша
➖если цитирований меньше — передвигаем левый указатель, рассматривая варианты справа

▫в конце возвращаем количество статей после левого указателя (n - l)

#solution275

🟡Medium
624. Maximum Distance in Arrays

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

Верните максимальное расстояние, как абсолютную разность |a - b|, выбрав два целых числа из двух разных массивов

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

173/200
#leetcode624 | #medium