Сначала выкладывается задача с подсказкой, затем решение с основной идеей

Цель — наработать базу алгоритмических задач для прохождения собеседований в крупные компании:
FAANG, Yandex, Sber, Ozon, VK и другие

Старт 1 июля

Задача уровня 🟢 Easy
1. Two sum

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

1/200
#easy
#leetcode1

Стартуем марафон с классической и самой первой задачи на LeetCode
Тем не менее, ее всё ещё спрашивают на собеседованиях, а позже мы разберем усложненную версию этой задачи, которую была на реальном собеседовании в Yandex

Задача уровня 🟢 Easy
217. Contains Duplicate

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

2/200
#easy
#leetcode217

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

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

📝 Идея
Проходимся по массиву, проверяя за O(1) есть ли в map нужный ключ (taget - nums[i]), при этом пока не найдем нужную пару, сохраняем в map (значение массива - индекс)

#solution1

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

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

📝 Идея
Проходимся по массиву, проверяя за O(1) содержится ли в set данный элемент, при этом сохраняем этот элемент для дальнейших проверок

#solution217

Задача уровня 🟢 Easy
242. Valid Anagram

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

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

3/200
#easy
#leetcode242

Задача уровня 🟡 Medium
49. Group Anagrams

Пример:

Input: ["eat","tea","tan","ate","nat","bat"]

Output: 
[["bat"], ["nat","tan"], ["ate","eat","tea"]]

Подсказка: что подойдет в качестве ключа в HashMap?

4/200
#medium
#leetcode49

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

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

📝 Идея
Используя код символа строки (с - 'a') получаем значение индекса массива и увеличиваем на единицу для строки S, для строки T уменьшаем на единицу
В итоге если массив весь в нулях - значит количество букв в обоих строках одинаково

#solution242

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

Time: O(n*klog(k))
Space: O(n)

📝 Идея
Для решения используем HashMap, в качестве пары ключ-значение используем отсортированную строку и ArrayList
Если раньше не встречалось данное отсортированное слово - просто создаем новый ArrayList, далее все строки складываем к своим ключам

#solution49

🟡 Medium
347. Top K Frequent Elements

Пример:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

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

5/200
#medium
#leetcode347

🟡 Medium
238. Product of Array Except Self

Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

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

6/200
#medium
#leetcode238

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

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

📝 Идея
1. Делаем map, где сохраняем для каждого элемента количество его появлений в массиве
2. Формируем массив частоты появлений элементов, то есть каждый элемент добавляется в список под индексом, соответствующем его частоте появления (от 1 до N)
3. Идем в обратном по массиву порядке считывая все значения для ответа

#solution347

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

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

📝 Идея
Если посчитать массив префиксных произведений получим:
[1, 2, 6, 24]
Постфиксных:
[24, 24, 12, 4]
Тогда элементы массива res[i] = prefix[i - 1] * suffix[i + 1]

В целях экономии памяти данный алгоритм высчитывает всё в одном массиве, при этом префиксное произведение сдвигается вправо, чтобы при обратном проходе элементы высчитывались на нужном месте
После первого цикла получаем массив res = [1, 1, 2, 6]
После второго res = [24, 12, 8, 6]

#solution238

🟡 Medium
128. Longest Consecutive Sequence

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Самая длинная последовательность последовательных элементов — [1, 2, 3, 4], ее длина равна 4.

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

7/200
#medium
#leetcode128

🟢 Easy
125. Valid Palindrome

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
"amanaplanacanalpanama" is a palindrome.

Input: s = "race a car"
Output: false
"raceacar" is not a palindrome.

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

8/200
#easy
#leetcode125

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