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

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

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

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

🟪далее делаем основную проверку, возвращая false, если:
➡️текущие символы в строках не равны, то есть последовательность L и R в строках неодинаковая
➡️текущий символ равен ‘L’ и его позиция в строке start меньше, чем в строке target, то есть он не сможет туда попасть, так как не может двигаться вправо
➡️текущий символ равен ‘R’ и его позиция в строке start больше, чем в строке target, то есть он не сможет туда попасть, так как не может двигаться влево

🟪если все условия прошли, увеличиваем оба указателя

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

👩‍💻 Java Algo | #solution2337

🟡Medium
80. Remove Duplicates from Sorted Array II

Company: 🪄📱❤️

📝Дан массив nums, отсортированный в неубывающем порядке.
Измените его так, чтобы первые k элементов составляли массив, в котором каждый элемент встречается не более двух раз. Относительный порядок элементов должен остаться прежним.

Необходимо решить задачу без использования дополнительной памяти и вернуть k в качестве ответа

💡: поддерживайте счетчик одинаковых элементов

#leetcode80 | #medium #twopointers

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

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

💡 Идея
➖инициализируем переменные l и r на первый элемент и счетчик одинаковых элементов count

➖проходим по массиву указателем r:

▫если текущий элемент равен предыдущему, увеличиваем count, иначе ставим значение 1
▫если count <= 2, копируем текущий элемент в позицию l и увеличиваем ее (то есть, если count > 2, текущий элемент просто пропускается)

➖таким образом в позиции l всегда записываются не более двух одинаковых элементов и можно вернуть конечное значение l, как ответ

👩‍💻 Java Algo | #solution80

🟡Medium
1229. Meeting Scheduler

Company: 📱🚖📱

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

Гарантируется, что никакие два слота доступности одного и того же человека не пересекаются друг с другом

💡: вычисляйте общий промежуток времени для текущих слотов

#leetcode1229 | #medium #premium #twopointers

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

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

💡 Идея
🟦в начале отсортируем массивы и проинициализируем два указателя на каждый из них

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

➖если общий слот больше или равен duration, возвращаем ответ, как начало промежутка плюс duration

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

🟦в конце возвращаем пустой список, если не нашлось подходящего промежутка времени

👩‍💻 Java Algo | #solution1229

🔴Hard
1163. Last Substring in Lexicographical Order

Company: 📱

📝Для заданной строки s вернуть последнюю подстроку в лексикографическом порядке

💡: сравнивайте символы двух подстрок c позиций i и j с учетом смещения k

#leetcode1163 | #hard #twopointers

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

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

💡 Идея

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

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

🟦заведем два указателя i = 0 и j = 1 на подстроки и переменную k – порядковый номер символа, который мы будем сравнивать в этих подстроках

🟦проходим по заданной строке, пока j + k меньше ее длины, и сравниваем текущие символы подстрок с позиций i и j, используя смещение k:

▫если символы равны – увеличиваем k, чтобы сравнивать следующие
▫если символ в подстроке с i больше (дальше в алфавитном порядке), передвигаем j на следующую позицию (j + k + 1) и обнуляем k
▫если символ в подстроке с j больше, передвигаем указатель i на максимальную из двух позиций: i + k + 1 и j (так как i + k может стать больше j, если встретилось много подряд идущих одинаковых символов), далее ставим j на позицию вперед (i + 1) и обнуляем k

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

👩‍💻 Java Algo | #solution1163

✔️ НАВИГАЦИЯ

✅Канал JA Roadmap с полной навигацией по постам

✅Соответствие эмодзи по компаниям

🟦Решение топ 200 задач на различные темы:
- Начало -
[1], [50], [100], [200]

Собранный список на LeetCode:
https://leetcode.com/problem-list/2orbqreg/

🟦Задачи по темам от Easy к Hard:
1. Array & Hash
2. Two pointers
3. Prefix sum
4. Sliding Window
5. Stack
6. LinkedList
7. Binary Search
8. Binary Tree
9. PriorityQueue
10. Backtracking
11. Graphs

➡️ Стартуем тему префиксных сумм

#prefixsum

🟢Easy
724. Find Pivot Index

Company: 📱🚖🏢

📝Дан массив целых чисел nums, верните самый левый индекс поворота или -1, если такого нет.

Индекс поворота — это индекс, для которого сумма всех чисел слева от индекса равна сумме всех чисел справа от индекса

💡: вычислите общую сумму массива

#leetcode724 | #easy #prefixsum

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

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

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

➖затем снова проходим по массиву и на каждом шаге считаем текущую (левую) сумму элементов, но перед этим делаем проверку:

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

➖в конце возвращаем -1, если подходящего индекса не нашлось

👩‍💻 Java Algo | #solution724

🟢Easy
1413. Minimum Value to Get Positive Step by Step Sum

Company: 📱

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

💡: найдите минимальное значение текущей суммы

#leetcode1413 | #easy #prefixsum

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

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

💡 Идея

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

➖проходим по массиву, считая текущую сумму и одновременно сохраняя минимальное значение, которое в ней появляется

➖в конце возвращаем результат, как min × (-1) + 1, при этом в случае, когда в массиве все элементы положительные, вернется правильный ответ 1, так как изначально в качестве минимума мы ставим 0

👩‍💻 Java Algo | #solution1413

🟢Easy
1422. Maximum Score After Splitting a String

Company: 🔍📱📱

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

Результатом разделения строки является количество нулей в левой подстроке плюс количество единиц в правой подстроке

💡: используйте выражение: score = количество нулей слева + (общее кол-во единиц - кол-во единиц слева)

#leetcode1422 | #easy #prefixsum

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

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

💡 Идея

➖главное выражение для ответа: кол-во нулей в левой подстроке + кол-во единиц в правой

➖представим кол-во единиц в правой подстроке, как общее кол-во единиц минус их кол-во слева, тогда при проходе по строке, необходимо найти наибольшую разницу кол-ва нулей и единиц слева, а в конце добавить общее кол-во единиц

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

➖после прохода увеличиваем кол-во единиц, если последний символ единица

➖возвращаем результат, как наибольшую разницу + общее кол-во единиц

👩‍💻 Java Algo | #solution1422

🟡Medium
974. Subarray Sums Divisible by K

Company: 🚖📱🏢

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

💡: cчитайте остатки от деления префиксных сумм на k

#leetcode974 | #medium #prefixsum

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

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

💡 Идея
🟦используя массив префиксных сумм prefix, подходящий остаток от деления суммы подмассива от i до j равен (prefix[j] – prefix[i]) % k = 0, что можно записать как prefix[j] % k = prefix[i] % k, то есть нужно найти, сколько раз встречались одинаковые остатки от деления префиксных сумм на k

🟦инициализируем переменные для результата и префиксной суммы и массив частот остатков mod размером k

🟦проходим по заданному массиву:
➖вычисляем текущий остаток от деления префиксной суммы на k: prefix = (prefix + num % k + k) % k, где +k необходимо, чтобы обработать отрицательные значения

➖добавляем к результату количество полученного остатка из массива mod, а затем увеличиваем его частоту для следующих проверок

👩‍💻 Java Algo | #solution974

🟡Medium
2270. Number of Ways to Split Array

Company: 🏢📱📱

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

Допустимое разделение — сумма элементов от начала массива до индекса i больше или равна сумме элементов от i + 1 до конца, при этом правая часть не должна быть пустой

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

#leetcode2270 | #medium #prefixsum

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

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

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

➖инициализируем три переменные: leftSum для суммы элементов слева, rightSum для суммы элементов справа и count для подсчета разделений

➖в начале leftSum равен 0, а rightSum общей сумме массива, поскольку слева нет элементов, а справа находится весь массив

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

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

👩‍💻 Java Algo | #solution2270

🟡Medium
3355. Zero Array Transformation I

Company: 🔍

📝Дан целочисленный массив nums и двумерный массив запросов queries, где queries[i] = [li, ri].

Для каждого queries[i] уменьшите все элементы подмассива в диапазоне [li, ri] на 1, при этом элемент не может стать меньше нуля.

Верните true, если после обработки всех запросов все элементы в массиве будут равны 0

💡: для каждого запроса обозначайте начало диапазона и его конец в отдельном массиве

#leetcode3355 | #medium #prefixsum

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

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

💡 Идея
➖инициализируем массив prefixMinus для обозначения границ запросов и проходим по всем запросам, отмечая в этом массиве начало диапазона и его конец:

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

➖далее проходим по исходному массиву и накапливаем общий минус для текущей позиции, добавляя значения из массива prefixMinus

➖для каждой позиции проверяем — хватило ли количество диапазонов, которые покрыли данный элемент, чтобы он стал меньше или равен 0 (к текущему элементу добавляем текущий общий минус), если нет — сразу возвращаем false

➖в конце возвращаем true, так как весь массив пройден и нужное условие выполнилось

👩‍💻 Java Algo | #solution3355