🟡 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

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

Time: O(nm)
Space: O(1)

💡 Идея
▫Проходя по строке S, возможны 4 ситуации соотнесения с шаблоном P:
1⃣Символы равны или символ шаблона P равен '?' — тогда увеличиваем оба указателя
2⃣Символ шаблона равен '*' — тогда мы сохраняем его позицию и соответствующую позицию match в строке S, а затем увеличиваем позицию шаблона (то есть заменяем '*' на пустую последовательность)
3⃣Символы не равны, но при этом уже встречалась '*' — тогда мы возвращаемся к сохраненным позициям на единицу вперед и увеличиваем позицию match, то есть попадая в этот случай, мы используем '*' в качестве последовательности символов и передвигаем только позицию строки S
4⃣Символы не равны, при этом '*' не было — тогда возвращаем false
▫После выполнения цикла обрабатываем случай, если в конце шаблона P остались '*', которые можно просто заменить на пустоту
▫В результате возвращаем true, если оба указателя достигли конца строк

📎Хороший пример, чтобы разобраться с алгоритмом:

s = "abcabczzzde", p = "*abc???de*"

#solution44

🟡 Medium
64. Minimum Path Sum

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

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

137/200
#medium
#leetcode64

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

Time: O(nm)
Space: O(1)

💡 Идея
🟪Начиная с первого столбца, заполняем первую строку, суммируя ячейки слева, так как в них можно прийти только таким способом
🟪Следуя такой же логике, заполняем первый столбец, только теперь суммируем элементы сверху
🟪Далее заполняем минимальными путями остальные ячейки, начиная с [1,1], суммируя с текущей минимальную из левой и верхней
🟪В результате в правой нижней ячейке получаем путь с минимальной суммой

#solution64

🟡 Medium
454. 4Sum II

📰 Даны четыре целочисленных массива, все имеют длину n, вернуть количество четверок индексов (i, j, k, l), таких что:
▫ 0 <= i, j, k, l < n
▫ nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

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

138/200
#medium
#leetcode454

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

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

💡 Идея
🟦Составляем HashMap из первых двух массивов, где ключом будет являться сумма отдельных элементов, а значением количество таких сумм
🟦Далее проходимся по оставшимся двум массивам и ищем в HashMap сумму, обратную num3 + num4, чтобы получить на выходе 0, и складываем в результат ее количество
🟦В итоге, в ответ просуммированы все варианты четверок элементов, сумма которых равна 0

#solution454

🟡 Medium
189. Rotate Array

📰 Дан целочисленный массив, поверните его вправо на k шагов, где k— неотрицательное число

Попробуйте реализовать решение, используя O(1) памяти

Подсказка: перед перестановкой элементов переверните части массива, разделенные k

139/200
#medium
#leetcode189

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

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

💡 Идея
🟪Предварительно реализуем функцию reverse, которая будет переворачивать часть массива по заданным границам
🟪В начале исключим вариант, что k больше n (длина массива), взяв для него остаток от деления на n
🟪Далее переворачиваем поочередно части массива, разделенные k:
▫ от 0 до n - k - 1, то есть первую часть массива
▫ от n - k до n - 1 — вторую часть массива
🟪Затем переворачиваем весь массив и получаем ответ

#solution189

🟡 Medium
209. Minimum Size Subarray Sum

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

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

140/200
#medium
#leetcode209

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

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

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

#solution209

🟡 Medium
394. Decode String

📰 Дана закодированная строка, вернуть ее декодированную.

Правило кодирования: k[string], где string внутри квадратных скобок повторяется ровно k раз, где k — гарантированно положительное целое число. Входная строка всегда соответствует данному формату.

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

141/200
#medium
#leetcode394