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

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

⚡️ Идея
▫для решения задачи используем bucket sort, где bucket будет формироваться как nums[i] / (valueDiff + 1) c округлением вниз, чтобы обработать отрицательные элементы

▫проблема, которую нужно решить — это проверка для элемента x наличия в текущем окне длиной indexDiff значения в диапазоне [x - valueDiff, x + valueDiff]

▫поэтому для каждого элемента проверяем, существует ли соседний или такой же bucket, поскольку любые два элемента, которые не удовлетворяют данному условию, точно имеют разность больше valueDiff

▫возвращаем true, если разность между элементом из bucket и текущим <= valueDiff или уже существует такой же bucket

▫добавляем (bucket, nums[i]) в HashMap и удаляем левый элемент из окна, если текущий индекс >= indexDiff

#solution220

🟡Medium
236. Lowest Common Ancestor of a Binary Tree

📝Дано бинарное дерево, найдите наименьшего общего предка для двух заданных узлов p и q (заданный узел также может являться предком)

💡: возвращайте некоторый флаг, если встретили p или q, обходя дерево в глубину

171/200
#leetcode236 | #medium

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

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

⚡️ Идея
▫реализуем функцию helper, которая проходит дерево в глубину и возвращает true, если поддерево содержит p или q

▫используем три переменные для отслеживания общего предка:
➖curr — отмечаем 1, если текущий узел равен p или q
➖left — отмечаем 1, если рекурсивный вызов функции для левого поддерева возвращает true
➖right — отмечаем 1, если рекурсивный вызов функции для правого поддерева возвращает true

▫если для текущего узла сумма трех переменных равна 2-м — значит мы нашли наименьшего общего предка

▫возвращаем true, если любая из трех переменных содержит p или q (их сумма больше 0)

#solution236

🟡Medium
275. H-Index II

📝Дан массив целых чисел citations, отсортированный по возрастанию, где citations[i] — количество цитирований, полученных исследователем для i-ой статьи.

Необходимо вернуть индекс Хирша исследователя с решением за O(logn) по времени

💡: реализуйте бинарный поиск, используя длину массива для перемещения указателей

172/200
#leetcode275 | #medium

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

Time: O(logn)
Space: O(1)

⚡️ Идея
▫реализуем бинарный поиск, в котором для перемещения указателей будем использовать на длину массива (n)

▫вычисляем mid, а затем сравниваем текущее значение цитирований с оставшимся количеством статей (n - mid) :
➖если цитирований больше — передвигаем правый указатель, пробуя увеличить индекс Хирша
➖если цитирований меньше — передвигаем левый указатель, рассматривая варианты справа

▫в конце возвращаем количество статей после левого указателя (n - l)

#solution275

🟡Medium
624. Maximum Distance in Arrays

📝Вам дан список массивов, где каждый отсортирован в порядке возрастания.

Верните максимальное расстояние, как абсолютную разность |a - b|, выбрав два целых числа из двух разных массивов

💡: сначала считайте результат, а затем обновляйте минимум и максимум

173/200
#leetcode624 | #medium

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

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

⚡️ Идея
▫в начале проинициализируем минимум и максимум, используя нулевой массив из списка

▫далее проходим по всему списку массивов, начиная с первого, и на каждом шаге делаем следующее:
➖считаем текущий результат, используя максимальный и минимальный элемент из массива — |a[0] - max| и |a[last] - min|
➖обновляем текущий минимум и максимум

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

#solution624

🟡Medium
280. Wiggle Sort

📝Дан массив целых чисел nums, отсортируйте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....

Необходимо решить задачу за O(n) по времени

💡: используйте свойство четной и нечетной позиций относительно левого элемента

174/200
#leetcode280 | #medium #premium

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

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

⚡️ Идея
🟦заметим, что на выходе значения на нечетных позициях должны быть всегда больше значений слева, а на четных позициях меньше

🟦используем этот факт и, проходя по массиву, меняем местами текущий и элемент слева, если:
➖позиция нечетная и текущий элемент меньше левого
➖позиция четная и текущий элемент больше левого

🟦такая замена не портит общую сортировку, так как мы только улучшаем позицию слева и выставляем правильное отношение в текущей

#solution280

🟢Easy
350. Intersection of Two Arrays II

📝 Даны два целочисленных массива nums1 и nums2, вернуть массив их пересечение.

Каждый элемент в результате должен появиться столько раз, сколько он появляется в обоих массивах. Можно вернуть результат в любом порядке

💡: используйте HashMap для массива меньшей длины

175/200
#leetcode350 | #easy

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

Time: O(n + m)
Space: O(min(n, m))

⚡️ Идея
🟦в начале выбираем меньший по длине массив, рекурсивно вызывая функцию, поменяв местами аргументы, если nums1 > nums2

🟦проходим по первому массиву и в HashMap формируем частоту элементов

🟦проходим по второму массиву и, если в HashMap частота текущего элемента больше нуля, ставим его в nums1[k], а затем увеличиваем k и уменьшаем частоту элемента

🟦в конце с помощью Arrays.copyOfRange(nums1, 0, k) возвращаем массив ответа от 0 до k (не включительно)

#solution350

🟡Medium
93. Restore IP Addresses

📝Дана строка, содержащая только цифры, вернуть все допустимые IP-адреса (в любом порядке), которые могут быть сформированы путем вставки точек.

Допустимый IP-адрес состоит ровно из четырех целых чисел, разделенных точками. Каждое целое число находится в диапазоне [0, 255] и не имеет ведущих нулей

💡: рассматривайте позиции точек, используя поход backtracking

176/200
#leetcode93 | #medium

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

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

⚡️ Идея
▫реализуем функцию backtrack для рассмотрения всех вариантов постановки точек

▫поскольку допустимый IP-адрес состоит из чисел в диапазоне [0, 255], можно рассматривать только три варианта постановки точки: после 1-ой, 2-ой и 3-ей цифры от текущей

▫поэтому для текущей позиции запускаем цикл на 3 вперед, составляя возможный вариант числа для IP-адреса и, если он подходит под условия, рекурсивно вызываем функцию backtrack, в которую передаем:
➖текущую позицию + 1
➖счетчик точек + 1
➖текущий IP-адрес, добавляя полученное число и точку
➖список результата

▫базовым случаем для функции будет являться количество точек, равное 4-м, и полностью пройденная строка, тогда добавляем текущий адрес в результат, убирая лишнюю точку в конце

#solution93

🟡Medium
2352. Equal Row and Column Pairs

📝Для заданной целочисленной матрицы вернуть количество пар, в которых строка и столбец равны.

Пара строк и столбцов считается равной, если они содержат одни и те же элементы в одном и том же порядке

💡: используйте HashMap, где ключом является строковое представление массива

177/200
#leetcode2352 | #medium

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

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

⚡️ Идея
▫проходим по строкам матрицы и сохраняем их частоту в HashMap, используя для ключа строковое представление массива Arrays.toString(row)

▫далее проходим по столбцам, формируя для каждого массив и его строковое представление, а затем добавляем
в результат значение из HashMap, если данный столбец встречался в виде строки

#solution2352

🟡Medium
1910. Remove All Occurrences of a Substring

📝Даны две строки — s и part, удаляйте самое левое вхождение подстроки part в s, пока не будут удалены все.

Верните s после всех операций

💡: используйте стек, проверяя в нем последние символы длиной part

178/200
#leetcode1910 | #medium

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

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

⚡️ Идея
🟦проходим по строке и кладем текущий символ в стек

🟦если текущий символ равен последнему в строке part и размер стека больше длины part (m):
➖формируем из стека строку длиной m и, если она не равна part, кладем ее обратно

🟦в конце формируем строку ответа из полученного стека


📎В комментариях решение в 5 строк, но за O(n²)
#solution1910

🟡Medium
120. Triangle

📝 Для заданного "cписка-треугольника" вернуть минимальную сумму пути сверху вниз.

Если вы находитесь в позиции i в текущей строке, вы можете перейти либо на такую же, либо на позицию i + 1 в следующей строке

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

179/200
#leetcode120 | #medium

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

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

⚡️ Идея
▫используем массив dp, который изначально представляет собой основание треугольника со всеми его значениями

▫затем, начиная с предпоследней строки, поднимаемся наверх и для каждого столбца составляем оптимальный путь следования, обновляя dp[j], как сумму текущего значения и минимума из следующей строки (dp[j] и dp[j + 1])

▫в результате прохода попадаем в вершину треугольника, то есть в нулевом элементе массива dp получаем минимальную сумму

#solution120

🟡Medium
1497. Check If Array Pairs Are Divisible by k

📝Дан массив целых чисел четной длины n и целое число k.

Верните true, если можно разделить массив ровно на n / 2 пары так, чтобы сумма каждой делилась на k

💡: используйте массив частот остатков от деления на k

180/200
#leetcode1497 | #medium

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

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

⚡️ Идея
▫составим массив частот freq остатков от деления на k:
➖проходим по массиву и для каждого числа вычисляем остаток от деления на k, при этом используем запись (num % k + k) % k, чтобы предотварить отрицательные значения

▫проходим по freq и, поскольку пар необходимо n / 2, то количество остатков i должно быть столько же, сколько и остатков k - i, поэтому возвращаем false, если условие нарушено

▫в конце отдельно проверяем нулевой остаток на четное количество, так как он является парой для самого себя

Для примера 1:

[1 2 3 4 5 10 6 7 8 9] — исходный массив
[1 2 3 4 0 0 1 2 3 4] — остатки от деления на k
[2 2 2 2 2] — массив частот остатков

#solution1497