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

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

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

💡 Идея
➖инициализируем указатели l — для прохода по массиву и r — для обозначения конца массива после удвоения нулей, а также end, который указывает на конец всех удвоений

➖первым проходом по массиву передвигаем r влево, если встретили 0

➖при этом, если l и r указывают на один и тот же элемент, равный 0 — ставим 0 в конец массива и уменьшаем end, так как при удвоении данного элемента, второй 0 не влезет в размер массива и нам не нужно его учитывать

➖далее проходим массив с end до 0 указателем i и смотрим на элементы под указателем r:
▫если равен 0, удваиваем его, копируя в i и i - 1
▫если не равен 0, просто копируем в i

👩‍💻 Java Algo | #solution1089

🟢Easy
541. Reverse String II

Company: 📱🔍📱

📝Даны строка s и целое число k. Поделите всю строку на части размером 2k и для каждой переверните первые k символов

💡: преобразуйте строку в массив символов

#leetcode541 | #easy #twopointers

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

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

💡 Идея
➖в начале преобразуем строку в массив символов с помощью s.toCharArray()

➖проходим по массиву указателем part с шагом 2k и для каждой такой части:

▫устанавливаем левый указатель в начало текущей части — part, а правый выбираем, как минимум из последнего индекса строки и (part + k - 1), обрабатывая возможный выход за пределы

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

➖в конце возвращаем ответ, преобразуя массив обратно в строку c помощью new String(arr)

👩‍💻 Java Algo | #solution541

🟢Easy
27. Remove Element

Company: 🔍🚖❤️

📝Дан массив целых чисел nums и целое число val. Вернуть количество элементов, которые не равны val.

При этом измените массив nums так, чтобы первые k элементов были не равны val, остальные элементы не важны, порядок может быть любой.

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

#leetcode27 | #easy #twopointers

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

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

💡 Идея
➖инициализируем переменную j = 0, которая будет показывать куда записывать элементы, не равные val, и count для подсчета их количества

➖проходим по массиву и, если текущий элемент не равен val:
▫записываем его в позицию j
▫увеличиваем j и count

➖в конце возвращаем count, при этом исходный массив изменен по условию

👩‍💻 Java Algo | #solution27

🟢Easy
925. Long Pressed Name

Company: 📱🔍

📝Ваш друг печатает name на клавиатуре. Иногда при наборе клавиша может залипать и символ будет напечатан 1 или более раз.

Верните true, если возможно, что typed — это попытка набрать name с возможным залипанием клавиш

💡: проверьте свой алгоритм на примере: name = "leelee", typed = "lleeelee" и учтите все возможные краевые случаи

#leetcode925 | #easy #twopointers

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

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

💡 Идея
➖инициализируем указатели i и j на начала name и typed, соответственно

➖проходим по строкам:

🟦если текущие символы на позициях i и j совпадают, и при этом i ещё не достиг конца строки name, увеличиваем оба указателя
🟦если символы не совпадают, но текущий символ в typed равен предыдущему, передвигаем указатель j, учитывая возможное залипание
🟦в любом другом случае сразу возвращаем false

➖выражение "i < конца строки" name в первом условии позволяет учесть случай, когда залип последний символ в typed (то есть будет двигаться только указатель j)

➖в конце возвращаем true, только если i равен концу строки, учитывая случай, когда в typed оказалось меньше символов

👩‍💻 Java Algo | #solution925