🔴 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

✅ Решение задачи 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