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

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

📝 Идея
1. Все элементы складываем в set
2. Проходимся по массиву, если элемент является начальным (т.е. элемента на единицу меньше нет) считаем длину последовательности
3. Сравниваем с текущим максимумом

#solution128

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

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

📝 Идея
Используем метод двух указателей: если элементы слева и справа строки неодинаковые: выводим false
Также по условию пропускаем элементы, которые не являются буквой или цифрой

#solution125

🟡 Medium
167. Two Sum II - Input Array Is Sorted

Пример:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Подсказка: задача на применение two pointers

9/200
#medium
#leetcode167

🟡 Medium
15. 3Sum

Пример:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

Различными триплетами являются [-1,0,1] и [-1,-1,2]. 

Подсказка: если зафиксировать одно значение - задача становится похожа на two sum

10/200
#medium
#leetcode15

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

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

📝 Идея
Используем метод двух указателей: поскольку массив изначально отсортирован - можно однозначно сказать, что если текущая сумму больше target, то остается только уменьшать правую границу, если сумма меньше - увеличиваем левую
Так, пока не найдем нужную пару

#solution167

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

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

📝 Идея
Используем принцип двух указателей, только теперь фиксируем один элемент и проходимся по оставшимся знакомым алгоритмом

Циклы while и блок с continue нужны для того, чтобы не было повторений триплетов

#solution15

🟡 Medium
11. Container With Most Water

Пример:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Подсказка: задача на использование two pointers

11/200
#medium
#leetcode11

🔴 Hard
42. Trapping Rain Water

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Подсказка: задача на использование two pointers

12/200
#hard
#leetcode42

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

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

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

#solution11

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

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

📝 Идея
▫️Двигаясь по массиву есть только две опции:
1. Столбец больше максимального, значит обновляем максимум
2. Столбец меньше максимального, значит добавляем в результат разницу между высотами, то есть объем воды
▫️При этом следим, чтобы левая граница была не меньше правой, чтобы вода не "переливалась"

#solution42

🟢 Easy
20. Valid Parentheses

Пример:

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

Подсказка: как можно использовать стек для решения?

13/200
#easy
#leetcode20

🟡 Medium
22. Generate Parentheses

Пример:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input: n = 1
Output: ["()"]

Подсказка: какое условие необходимо для правильно сформированных скобок?

14/200
#medium
#leetcode22

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

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

📝 Идея
▫️Перебираем строку и записываем в стек скобку противоположную открытой, теперь если встретилась закрытая скобка, то если на вершине стека на не такая же скобка или он вообще пуст, значит последовательность неправильная
▫️В конце методом .isEmpty() проверяем, что в стеке не осталось открытых скобок

#solution20

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

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

📝 Идея
▫️Реализуем функцию backtrack для перебора всех вариантов правильных скобок
▫️Главным условием создания правильной скобочной последовательности является то, что текущее количество открытых скобок больше или равно количеству закрытых, то есть закрытая скобка никогда не будет добавляться раньше открытой. Отсюда два варианта:
1️⃣ Если количество открытых скобок меньше n добавляем "(" в curr
2️⃣ Если количество открытых скобок больше количества закрытых добавляем ")" в curr
Далее запускаем рекурсию, после удаляем последний элемент, чтобы проверить все варианты скобочной последовательности
▫️Базовый случай в данном алгоритме - количество закрытых скобок равно n

#solution22

🟡 Medium
739. Daily Temperatures

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Подсказка: задача на использование стека

15/200
#medium
#leetcode739

🟡 Medium
853. Car Fleet

Пример:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3

▪️Автомобили, стартующие c 10 (скорость 2) и 8 (скорость 4), образуют автопарк, встречающийся в 12
▪️Автомобиль, стартующий с 0 (скорость 1), не догоняет ни один другой автомобиль, поэтому он сам по себе является автопарком.
▪️Автомобили, стартующие с 5 (скорость 1) и 3 (скорость 3), образуют автопарк, встречающийся в точке 6 и двигаются со скоростью 1, пока не достигнут target

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

16/200
#medium
#leetcode853

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

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

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

#solution739

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

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

📝 Идея
▫️Создаем двумерный массив pairs, куда складываем пары position-speed и сортируем его по позициям
▫️Так как машины не могут обгонять, а только упираться друг в друга - идем с конца массива, делая проверку:
- Если время прихода в target текущей машины меньше или равно следующей, значит она ее догонит и образуется автопарк, соответственно уменьшаем максимально возможное количество (то есть n)
- Иначе обновляем текущее время прихода машины для следующих проверок

#solution853

🟢 Easy
121. Best Time to Buy and Sell Stock

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 5

Input: prices = [7,6,4,3,1]
Output: 0

Подсказка: используйте подход sliding window для решения за O(n)

17/200
#easy
#leetcode121

🔴 Hard
84. Largest Rectangle in Histogram

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10

Подсказка: в каком случаем столбец может расширяться дальше и как можно сохранять индексы?

18/200
#hard
#leetcode84

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

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

📝 Идея
▫️Для максимальной выгоды нам необходим день день с минимальной ценой, поэтому используя подход sliding windows проходимся по массиву, обновляя день с минимальной ценой и считая максимальную выгоду, как разницу цен в текущем дне и минимальной ценой
▫️Если все цены будут идти по убыванию, соответственно разница всегда будет отрицательной и ответ будет 0

#solution121