🟢Easy
1331. Rank Transform of an Array

Company: 📱🔍

📝Дан массив целых чисел, замените каждый элемент его рангом.

Ранг показывает, насколько велик элемент и имеет следующие правила:
➖начинается с 1
➖чем больше элемент, тем больше ранг. Если два элемента равны, их ранги должны быть одинаковыми
➖ранг должен быть как можно меньше

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

#leetcode1331 | #easy #array #hash

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

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

💡 Идея
➖создадим клон массива и отсортируем его

➖проходим по новому массиву и сохраняем в HashMap [sortArr[i] — rank], при этом ранг увеличиваем только, если текущий элемент больше предыдущего

➖в конце обновляем исходный массив, заменяя элементы на их ранги, взятые из значений HashMap

👩‍💻 Java Algo | #solution1331

🟢Easy
219. Contains Duplicate II

Company: 🔍📱❤️

📝Дан массив целых чисел nums и целое число k.

Вернуть true, если в массиве есть два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k

💡: поддерживайте set размером k

#leetcode219 | #easy #array #hash

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

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

💡 Идея
➖используем HashSet, который будем поддерживать размером k, чтобы при обнаружении одинаковых элементов точно знать, что они находятся на нужном расстоянии

➖проходим по массиву:
▫если текущий элемент содержится в set, возвращаем true
▫добавляем текущий элемент в set
▫если размер set больше k, удаляем самый левый элемент (nums[i - k])

➖в конце возвращаем false, так как массив полностью пройден и подходящих элементов не нашлось

📎В комментариях код с использованием HashMap

👩‍💻 Java Algo | #solution219

🟡Medium
532. K-diff Pairs in an Array

Company: 🔍📱🚖

📝Дан массив целых чисел nums и целое число k, верните количество уникальных пар k-diff в массиве.

Пара k-diff — это пара (nums[i], nums[j]), для которой верны следующие условия:
➖0 <= i, j < nums.length
➖i != j
➖abs(nums[i] - nums[j]) == k

💡: для поиска уникальных пар перебирайте ключи HashMap

#leetcode532 | #medium #array #hash

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

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

💡 Идея
🟦создадим и заполним HashMap частот, которая хранит уникальные элементы в качестве ключей и количество их появлений в массиве в качестве значений

🟦затем перебираем ключи HashMap:

▫если k > 0, проверяем наличие в хэш-карте (k + key). Используя только сложение, мы исключаем возможность появления дубликатов, то есть если мы нашли пару (1,3), мы не будем учитывать (3,1)

▫если k == 0, необходимо проверить, что количество появлений в массиве текущего элемента больше 1, тогда при вычитании одинаковых элементов можно получить 0

▫при выполнении условия увеличиваем количество пар и в результате получаем ответ

👩‍💻 Java Algo | #solution532

🟡Medium
1711. Count Good Meals

Company: 🔍

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

Вернуть результат по модулю (10⁹ + 7)

Ограничения:

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

💡: для каждого элемента примените идею TwoSum, где target будет равен всем степеням двойки из условия

#leetcode1711 | #medium #array #hash

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

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

💡 Идея
➖поскольку по условию значения элементов массива не превосходят 2²⁰, задача сводится к поиску пар чисел, сумма которых является степенью двойки

➖проходим по всем элементам массива и для каждого:
▫перебираем все степени двойки (target) от 0 до 21, так как максимально возможная сумма двух элементов (2²⁰ + 2²⁰) не превысит 2²¹

▫если в HashMap содержится (target - num), добавляем в результат значение по данному ключу, тем самым учитывая все возможные варианты составления пар

▫делим текущий результат по модулю на (10⁹ + 7), чтобы избежать переполнения и выполнить условие

▫после проверки всех степеней двойки для текущего элемента — добавляем его в HashMap, увеличивая значение на 1

👩‍💻 Java Algo | #solution1711

🟡Medium
3185. Count Pairs That Form a Complete Day II

Company: 📱

📝Дан целочисленный массив hours, представляющий время в часах, вернуть количество пар (i, j), где i < j и hours[i] + hours[j] образуют полный день.

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

💡: для текущего элемента ищите необходимый остаток, чтобы дополнить его до числа кратного 24

#leetcode3185 | #medium #array #hash

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

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

💡 Идея
➖инициализируем массив count, в котором будем хранить количество остатков от деления на 24

➖проходим по массиву и для каждого элемента:
▫вычисляем необходимый остаток, чтобы в сумме получить число кратное 24, то есть ищем значение (24 - num % 24) и дополнительно берем его по модулю 24, чтобы обработать случай, когда num кратно 24

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

▫увеличиваем ячейку count для текущего элемента по модулю 24

👩‍💻 Java Algo | #solution3185

🟡Medium
3371. Identify the Largest Outlier in an Array

Company: 📱🔍

📝Вам дан массив целых чисел, который содержит n элементов, где ровно (n - 2) элементов — это специальные числа . Один из оставшихся двух элементов — это сумма специальных чисел, а другой — выброс.

Выброс определяется как число, которое не является ни одним из специальных чисел, ни элементом, представляющим сумму этих чисел.

Верните наибольший выброс из массива

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

#leetcode3371 | #medium #array #hash

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

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

💡 Идея
➖для начала проходим по всему массиву и считаем общую сумму, параллельно записывая каждое значение в HashMap частот элементов

➖затем проходим по ключам HashMap и каждый проверяем на возможный выброс:
▫вычисляем сумму check, как общую без текущего элемента

▫обновляем результат, если сумма check четная и выполняется одно из условий:
1⃣половина check равна текущему элементу и элемент встречается больше 1-го раза
2⃣половина check отличается от текущего элемента и в HashMap существует данный ключ

👩‍💻 Java Algo | #solution3371

🟡Medium
3404. Count Special Subsequences

Company: 🔍

📝Дан массив nums, состоящий из положительных целых чисел.

Специальная подпоследовательность — это индексы (p, q, r, s), где p < q < r < s, которые удовлетворяют следующим условиям:
▫nums[p] * nums[r] == nums[q] * nums[s]
▫между каждой парой индексов должен быть хотя бы один элемент: q - p > 1, r - q > 1 и s - r > 1.

Верните количество различных специальных подпоследовательностей

Ограничения:

7 <= nums.length <= 1000

💡: выберите начальную позицию r и от нее передвигайте все индексы, сохраняя нужные соотношения: (nums[s] / nums[r]) и (nums[p] / nums[q])

#leetcode3404 | #medium #array #hash

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

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

💡 Идея
🟦в качестве главного выражения поменяем исходное на nums[s]/nums[r] == nums[p]/nums[q], чтобы удобно было перемещать указатели

🟦выберем начальную позицию r, как максимальную, но подходящую под условия, то есть r = nums.length - 3, и от нее будем двигаться к минимальной r = 4

🟦от этой позиции расставляем остальные указатели, от которых будем проводить поиск соотношений:
▫s ставим на позицию r + 2 и циклом двигаемся до конца массива
▫q ставим на позицию r - 2
▫p ставим на позицию 0 и циклом двигаемся до (q - 1)

🟦во время перебора указателей s — сохраняем в HashMap соотношения nums[s]/nums[r], отмечая их количество

🟦во время перебора указателей p увеличиваем результат на количество соотношений nums[p]/nums[q], если такое содержится в HashMap

👩‍💻 Java Algo | #solution3404

🖼Иллюстрация к решению задачи 3404

Расстановка и передвижение указателей (p, q, r, s)

#figure #array #hash

🔴Hard
2488. Count Subarrays With Median K

Company: 🔍

📝Вам дан массив размером n, состоящий из различных целых чисел от 1 до n, и положительное число k.

Верните количество непустых подмассивов, медиана которых равна k.

Медиана массива — это средний элемент после сортировки массива по возрастанию. Если массив имеет четную длину, медианой является левый средний элемент.

Например:

медиана [2,3,1,4] — 2
медиана [8,4,3,5,1] — 4

💡: ведите переменную баланса, которую будете увеличивать, если текущий элемент больше k и уменьшать, если меньше

#leetcode2488 | #hard #array #hash

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

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

💡 Идея
➖инициализируем переменную balance, которая показывает соотношение элементов относительно k:
▫balance < 0 — элементов меньше k больше
▫balance > 0 — элементов больше k больше
▫balance == 0 — равное количество

➖проходим по массиву и на каждом шаге обновляем balance, сохраняя в HashMap его количество, пока не наткнулись на k

➖как только встретили k, начинаем считать количество подмассивов, складывая из HashMap:
▫количество текущего balance, что позволит составить подмассив с медианой k
▫количество balance - 1, учитывая случай, когда длина подмассива четная

📎Логика после нахождения ķ:

➖Если в HashMap содержится текущее значение balance, значит мы можем отбросить часть массива, которая дала такое значение, чтобы получить balance = 0, то есть подмассив с медианой k ровно посередине

➖И, если содержится balance - 1, значит при отбрасывании данной части массива, можно получить на 1 элемент больше справа от k, то есть медиану k, как левый средний элемент

👩‍💻 Java Algo | #solution2488

🔴Hard
1224. Maximum Equal Frequency

Company: 🔍

📝Дан целочисленный массив.

Вернуть максимально возможную длину префикса, где после удаления ровно одного элемента все оставшиеся встречаются одинаковое количество раз

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

#leetcode1224 | #hard #array #hash

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

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

💡 Идея

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

🟦инициализируем две HashMap: для частоты элементов и количества чисел с такой частотой

🟦проходим по массиву и на каждом шаге:
➖заполняем обе HashMap

➖вычисляем длину подмассива, который можно составить из частоты текущего элемента и количества чисел с такой частотой, перемножая эти два значения, а затем сравниваем ее с длиной префикса от начала:

▫если получили равную длину, значит можно добавить любой элемент справа и обновить результат, как длину префикса + 1
▫если получили длину на 1 меньше, значит в подмассиве есть элемент с частотой 1 и можно обновить результат, как текущую длину префикса

👩‍💻 Java Algo | #solution1224

➡️ Стартуем тему двух указателей

#twopointers

🟢Easy
1089. Duplicate Zeros

Company: 📱📱🚖

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

Элементы, выходящие за пределы длины исходного массива, не сохраняются.
Необходимо выполнить данные действия на месте, без дополнительной памяти

💡: найдите позицию конца массива после удвоения нулей

#leetcode1089 | #easy #twopointers