🟢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

🟡Medium
3026. Maximum Good Subarray Sum

Company: 📱🔍

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

Верните максимальную сумму хорошего подмассива

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

#leetcode3026 | #medium #prefixsum

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

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

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

🟦проходим по массиву, накапливаем текущую сумму и для каждого элемента проверяем, содержится ли в HashMap значение +k или -k от него

🟦если содержится, считаем максимальный результат, как текущая сумма минус сумма из HashMap

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

🟦при этом кладем в HashMap текущий элемент, только если его там нет или, если префиксная сумма для данного элемента больше текущей

👩‍💻 Java Algo | #solution3026

🔴Hard
798. Smallest Rotation with Highest Score

📝Вам дан массив nums, вы можете повернуть его на целое число k влево. После этого элементы, которые меньше или равны своему индексу, оцениваются в один балл.

Верните число k, которое соответствует наивысшему результату, который можно получить после применения поворота. Если есть несколько ответов, верните наименьшее k

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

#leetcode798 | #hard #prefixsum

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

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

💡 Идея
🟦создаем массив diff[] размером n, который будет хранить изменения количества баллов при каждом сдвиге

🟦далее проходим по массиву и для каждого элемента рассчитываем, при каком сдвиге данный элемент перестанет давать баллы: k = (i - nums[i] + 1 + n) % n, а затем уменьшаем diff[k] на 1, чтобы учесть, что при таком сдвиге баллы уменьшаются

🟦теперь будем накапливать изменения для каждого сдвига от 1 до n, проходя по массиву diff и суммируя их, при этом учитываем, что каждый новый элемент дает +1 балл, потому что в конец массива попадает новый элемент, который точно дает баллы, так как элементы массива по условию от 0 до n

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

❔Почему k вычисляется именно так?
▫i: исходная позиция элемента
▫- nums[i]: смещаемся назад настолько, насколько велик сам элемент
▫+ 1: смещаемся еще на одну позицию, чтобы теперь элемент не давал баллы
▫+ n: гарантируем, что выражение не будет отрицательным
▫% n: берем по модулю, чтобы остаться в пределах массива

❔Почему изменения для каждого сдвига суммируются?
➖вычисляя k, мы определяем самую правую позицию, в которой данный элемент не приносит баллы, соответственно при большем сдвиге он сдвигается левее, где также не будет приносить баллы, поэтому мы последовательно суммируем изменения для каждого сдвига. При этом мы учитываем, что массив цикличный, на каждом шаге добавляя в cur +1 для элемента, который перешел в конец массива

👩‍💻 Java Algo | #solution798

➡️ Стартуем тему скользящего окна

💡 Идея

Представим, что ты следишь за своими расходами и всегда хочешь знать, сколько денег ты потратил за последние 7 дней.

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

Таким образом, у тебя всегда актуальная сумма за последние 7 дней без необходимости считать ее всю постоянно.

#slidingwindow

🟢Easy
1652. Defuse the Bomb

Company: 🏢📱📱

📝Дан массив code и целое число k.

Необходимо заменить каждый элемент по следующим правилам:
▫если k > 0, замените элемент суммой следующих k чисел
▫если k < 0, замените элемент суммой предыдущих k чисел
▫если k == 0, замените элемент на 0

Массив code является круговым, поэтому следующим элементом code[n-1] является code[0], а предыдущим элементом code[0] является code[n-1].

Верните полученный массив

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

#leetcode1652 | #easy #slidingwindow

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

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

💡 Идея
🟦инициализируем массив для записи результата размером исходного (n) и сразу возвращаем его, если k == 0

🟦инициализируем два указателя: на начало окна start = 1 и конец end = k, но если k < 0, меняем позиции на start = n - |k| и end = n - 1, то есть устанавливая окно перед нулевым элементом

🟦далее считаем сумму в полученном окне, чтобы затем эффективно считать остальные

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

▫из текущей суммы вычитаем элемент на позиции старта окна (start % n) и добавляем элемент следующий после конца ((end + 1) % n), то есть считаем сумму для следующего окна, меняя только границы, при этом все содержимое между остается неизменным, поэтому мы получаем ее правильно

▫затем увеличиваем указатели start и end, фактически передвигая окно на следующую позицию

🟦в конце возвращаем полученный массив c результатом

👩‍💻 Java Algo | #solution1652

🟢Easy
2379. Minimum Recolors to Get K Consecutive Black Blocks

Company: 🔍📱💻

📝Дана строка, которая содержит символы 'W' и 'B', представляющие белый и черный цвета соответственно. Также дано целое число k— желаемое количество последовательных черных блоков.

За одну операцию вы можете перекрасить белый блок в черный.

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

💡: найдите минимальное количество белых блоков в окне

#leetcode2379 | #easy #slidingwindow

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

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

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

🟦проходим по строке и увеличиваем счетчик, если текущий символ 'B'

🟦как только, индекс стал больше или равен k, значит мы уже вышли за пределы окна и нужно удалить элемент слева: уменьшаем счетчик, если символ i - k = 'B'

🟦на каждом шаге проверяем минимальное количество белых блоков, как длину окна (k) минус количество черных блоков

👩‍💻 Java Algo | #solution2379