🟢 Easy
66. Plus One

📰 Вам дано большое целое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это цифра данного числа. Число не содержит ведущих нулей.

Увеличьте данное число на единицу и верните полученный массив цифр

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

116/200
#easy
#leetcode66

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

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

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

#solution66

🟡 Medium
73. Set Matrix Zeroes

📰 Дана целочисленная матрица, необходимо преобразовать матрицу: если элемент равен 0 — присвоить всей строке и столбцу значение 0.
Необходимо решить задачу с использованием O(1) памяти

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

117/200
#medium
#leetcode73

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

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

💡 Идея
▫️Чтобы не использовать дополнительную память — подойдет пометка нулевого элемента в строках и столбцах, но только необходимо учесть, что клетка [0][0] будет отвечать сразу и за столбец и за строку, поэтому первую строку пометим отдельно в переменной
▫️После пометок повторно проходимся по матрице и, если нулевой элемент в строке или столбце равен 0, текущий элемент также приравниваем нулю
▫️Затем отдельно заполняем нулями первый столбец и строку, если это необходимо

#solution73

🟡 Medium
54. Spiral Matrix

📰 Дана матрица, вернуть все ее элементы в "спиральном" порядке

Подсказка: просто смоделируйте сам процесс

118/200
#medium
#leetcode54

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

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

💡 Идея
▫️Инициализируем четыре указателя:
l — на первый столбец, r — на последний;
top — на первую строку, bottom — на последнюю
▫️Далее моделируем весь процесс с условием, что указатели не перекрывают друг друга:
- проходим по первой строке и смещаем указатель top
- проходим по последнему столбцу и смещаем указатель r
- проходим по последней строке и смещаем указатель bottom
- проходим по первому столбцу и смещаем указатель l
▫️В середине делаем дополнительную проверку на случай, если условие уже не выполняется

#solution54

🔴 Hard
149. Max Points on a Line

📰 Дан массив, где points[i] = [xi, yi] представляет точку на плоскости XY, вернуть максимальное количество точек, лежащих на одной прямой

Подсказка: для вычисления точек на одной прямой — (y2 - y1) / (x2 - x1)

119/200
#hard
#leetcode149

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

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

💡 Идея
▫️Для каждой пары точек вычисляем их наклон по формуле: (y2 - y1) / (x2 - x1), перед этим делая проверку на нулевой знаменатель и числитель
▫️Кладем полученное значение в HashMap и увеличиваем количество точек, находящееся с данным наклоном
▫️Параллельно проверяем максимальный результат, который можно получить

#solution149

🟡 Medium
443. String Compression

📰 Дан массив символов chars, сожмите его, используя следующий алгоритм:
- если длина группы равна 1, добавьте символ к строке s
- иначе добавьте символ, а затем длину группы

Строка s должна храниться во входном массиве символов, а не возвращаться отдельно.
Верните длину сжатой строки s, при этом используя O(1) памяти

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

120/200
#medium
#leetcode443

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

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

💡 Идея
▫️Начиная с позиции i = 0, запускаем цикл на подсчет длины последовательности
▫️Далее на позиции ind устанавливаем текущий символ и следующие элементы массива заполняем полученным числом длины последовательности в символьном виде
▫️Затем увеличиваем текущую позицию i на длину найденной последовательности

#solution443

🟡 Medium
1493. Longest Subarray of 1's After Deleting One Element

📰 Дан массив, состоящий из 0 и 1.
Верните размер самого длинного подмассива, содержащего только единицы после удаления одного элемента.

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

121/200
#medium
#leetcode1493

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

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

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

#solution1493

🟢 Easy
387. First Unique Character in a String

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

Подсказка: подсчитывайте количество каждого символа в строке

122/200
#easy
#leetcode387

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

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

💡 Идея
▫️Первым проходом по строке считаем количество каждого символа, используя массив размером 26
▫️Для обращения к индексу массива — необходимо от текущего символа отнять значение кода символа 'a', тогда для всех строчных букв будем получать значения от 0 до 25
▫️Вторым проходом по строке смотрим, если символ встречался только 1 раз — возвращаем его индекс

#solution387

🟡 Medium
560. Subarray Sum Equals K

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

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

123/200
#medium
#leetcode560

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

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

💡 Идея
▫️Идем по массиву и считаем текущую сумму
▫️Проверяем — если в HashMap лежит сумма, равная текущей сумме минус k, значит мы можем ее отбросить, чтобы текущая сумма равнялась k, и увеличить результат на количество таких сумм
▫️Текущую сумму кладем в HashMap в качестве ключа, а в значение записываем количество таких сумм
▫️Изначально в map под суммой 0 кладем 1, так как текущая сумма может равняться числу k

Пример: nums = [4, 1, 3, 2], k = 5

4 1 3 2
sum: 4 5 8 10
sum - k: -1 0 3 5
res: 0 1 1 2

#solution560

🟢 Easy
392. Is Subsequence

📰 Даны строки s и t, вернуть true, если s является подпоследовательностью t

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

124/200
#easy
#leetcode392

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

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

💡 Идея
▫️Инициализируем указатель i = 0
▫️Проходим по строке t, в случае равенства текущего символа t и символа строки s под указателем i — передвигаем его вправо, увеличивая на 1
▫️Если указатель i стал равным длине строки s — возвращаем true

#solution392

🟡 Medium
438. Find All Anagrams in a String

📰 Даны две строки s и p, вернуть список всех начальных индексов подстрок в s, которые являются анаграммой p

Подсказка: используйте sliding window c подсчетом частоты букв

125/200
#medium
#leetcode438

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

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

💡 Идея
▫️Проходим по строке P и подсчитываем частоту символов, используя массив
▫️Далее проходим по строке S до длины строки P и записываем частоту символов в этом диапазоне для формирования скользящего окна
▫️После проходим оставшуюся часть строки S, увеличивая частоту нового символа и уменьшая частоту символа слева
▫️На каждом шаге проверяем: если массивы частот двух строк идентичны, значит текущее окно строки S является анаграммой строки P и можно записать в ответ его начальный индекс

#solution438

🟡 Medium
523. Continuous Subarray Sum

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

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

126/200
#medium
#leetcode523