🟡 Medium
523. Continuous Subarray Sum

📰 Дан целочисленный массив и целое число k, вернуть true, если существует такой подмассив, длина которого не менее двух и его сумма кратна k

Подсказка: используйте префиксную сумму и HashMap

126/200
#medium
#leetcode523

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

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

💡 Идея
▫️Идем по массиву и считаем текущую сумму
▫️Проверяем: если в HashMap лежит остаток от деления текущей суммы на K, значит мы можем отбросить эту сумму, которая дала такой остаток, чтобы получить сумму кратную K и вернуть true
▫️При этом по условию длина подмассива должна быть не менее двух, поэтому дополнительно проверяем расстояние между текущим индексом и индексом найденной суммы, используя значение HashMap

#solution523

🟡 Medium
849. Maximize Distance to Closest Person

📰 Вам дан массив, где 1 представляет собой занятое место, 0 — свободное. Есть как минимум одно свободное место и как минимум один сидящий человек.
Алекс хочет сесть так, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.

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

Подсказка: сохраняйте позицию единицы и рассмотрите все случаи

127/200
#medium
#leetcode849

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

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

💡 Идея
▫️Проходим по массиву и, встретив единицу, проверяем:
- если сохраненная позиция единицы равна -1, значит это первая единица и максимальный результат будет, если посадить Алекса в начало
- иначе проверяем максимальное расстояние, если посадить Алекса между занятыми местами (1)
- затем сохраняем позицию единицы
▫️В конце рассматриваем еще один случай — проверяем расстояние, если посадить Алекса в самый конец

#solution849

🟢 Easy
977. Squares of a Sorted Array

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

Необходимо реализовать решение за O(n) по времени

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

128/200
#easy
#leetcode977

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

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

💡 Идея
▫️Инициализируем новый массив для сохранения результата
▫️Проходим исходный массив с конца и с помощью двух указателей проверяем абсолютные значения элементов с левого и правого краев массива
▫️Выбираем наибольшее из них и записываем в новый массив квадрат данного элемента, а затем передвигаем соответствующий указатель

#solution977

🟡 Medium
1004. Max Consecutive Ones III

📰 Дан двоичный массив и целое число k.
Верните максимальное количество последовательных единиц в массиве, если можно инвертировать не более k нулей

Подсказка: используйте подход sliding window

129/200
#medium
#leetcode1004

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

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

💡 Идея
▫️Для решения используем скользящее окно, в котором количество нулей будет не больше K
▫️Для этого идем по массиву и ведем подсчет количества нулей. Если значение стало больше K — передвигаем левую часть окна, пока не уменьшим его, встретив ноль
▫️На каждом шаге сравниваем размер окна с текущим максимальным результатом

#solution1004

🟢 Easy
228. Summary Ranges

📰 Вам дан отсортированный массив уникальных чисел.

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

Каждый диапазон [a,b] в списке должен быть представлен как:

1) "a", если a == b
2) "a->b", если a != b

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

130/200
#easy
#leetcode228

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

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

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

#solution228

🟡 Medium
34. Find First and Last Position of Element in Sorted Array

📰 Дан массив целых чисел, отсортированный в неубывающем порядке. Найдите начальную и конечную позицию заданного target значения.
Если target не найдено в массиве, вернуть [-1, -1].

Необходимо реализовать решение за O(logN) по времени

Подсказка: используйте модификацию бинарного поиска в зависимости от того, какую позицию ищите

131/200
#medium
#leetcode34

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

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

💡 Идея
▫️Используем обычный бинарный поиск, но передаем булевый параметр, который показывает какой элемент мы ищем (первый или последний):
- если он равен true, значит после равенства mid и target сдвигаемся влево для поиска первого элемента
- иначе — вправо
▫️Данный алгоритм можно хорошо понять на примере:

nums = [8, 8, 8, 8, 8], target = 8

#solution34

🟡 Medium
179. Largest Number

📰 Дан массив неотрицательных целых чисел, расположите их так, чтобы они образовали наибольшее число и верните его в виде строки

Подсказка: используйте факт, что если для чисел A, B — AB > BA, тогда ACB > BCA для любого C

132/200
#medium
#leetcode179

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

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

💡 Идея
▫️Инициализируем и заполняем массив строковых представлений чисел заданного массива
▫️Затем сортируем его, используя свой компаратор, который сравнивает порядок соединения чисел и выбирает больший результат
▫️В конце просто проходимся по всему отсортированному массиву и соединяем строковые представления чисел

#solution179

🟡 Medium
162. Find Peak Element

📰 Дан целочисленный массив, найти пиковый элемент и вернуть его индекс. Если массив содержит несколько пиков, вернуть индекс любого.
Пиковый элемент — это элемент, который строго больше своих соседей.

Необходимо реализовать решение за O(logN) по времени

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

133/200
#medium
#leetcode162

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

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

💡 Идея
▫️Используем обычный бинарный поиск, но после вычисления mid передвигаем указатели следующим образом:
- если следующий элемент меньше текущего, значит ищем пиковый элемент слева и передвигаем указатель R
- иначе — справа и передвигаем указатель L
▫️Если указатели совпали, значит элемент найден и можно возвращать ответ

Пример для nums = [1, 2, 3, 1]:

1, 2, 3, 1 —>
L M R

1, 2, 3, 1 —>
L R
M

1, 2, 3, 1
L
R
M

#solution162

🟡 Medium
395. Longest Substring with At Least K Repeating Characters

📰 Для заданной строки S и целого числа K вернуть длину самой длинной подстроки, такой, что частота каждого символа в этой подстроке больше или равна k

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

134/200
#medium
#leetcode395

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

Time: O(n^2)
Space: O(n)

💡 Идея
▫️Инициализируем массив частот символов и заполняем его, проходя по строке
▫️Затем снова проходим по строке и, если частота символа меньше k — разделяем строку на две части и вычисляем результат для каждой из них, рекурсивно вызывая исходную функцию
▫️В результате получим ответ, представляющий собой максимальный из разделенных частей строки или всю длину строки, если все символы встречаются хотя бы k раз

#solution395

🟡 Medium
334. Increasing Triplet Subsequence

📰 Дан целочисленный массив nums, вернуть true, eсли существует тройка индексов (i, j, k) такая, что i < j < k и nums[i] < nums[j] < nums[k]

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

135/200
#medium
#leetcode334

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

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

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

#solution334

🔴 Hard
44. Wildcard Matching

📰 Для входной строки s и шаблона p реализуйте сопоставление, где:
'?' — cоответствует любому отдельному символу;
'*' — соответствует любой последовательности символов (включая пустую последовательность);
Сопоставление должно охватывать всю входную строку (не частично)

Подсказка: запоминая позицию '*', проверяйте два случая: замена ее на пустую и заполненную последовательность

136/200
#hard
#leetcode44