Задача с собеседования в OpenText

У тебя есть бомба, которую нужно обезвредить, и времени остаётся всё меньше! Твой информатор передаст тебе круговой массив code длиной n и ключ k.
Чтобы расшифровать код, необходимо заменить каждое число. Все числа заменяются одновременно.

- если k > 0, замени i-е число суммой следующих k чисел.
- если k < 0, замени i-е число суммой предыдущих -k чисел.
- если k == 0, замени i-е число на 0.

Так как массив круговой, следующий элемент после code[n-1] - это code[0], а предыдущий элемент после code[0] - это code[n-1].
Даны круговой массив и целое число k. Верни расшифрованный код, чтобы обезвредить бомбу!

Пример 1:
Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Каждое число заменяется суммой следующих трёх чисел. Расшифрованный код: [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Обрати внимание, что числа берутся по кругу.

Пример 2:
Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: Когда k равно нулю, все числа заменяются на 0.

Пример 3:
Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: Расшифрованный код: [3+9, 2+3, 4+2, 9+4]. Обрати внимание, что числа снова идут по кругу. Если k - отрицательное, сумма берётся от предыдущих чисел.

Ограничения:
n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
При наивном решении мы бы проходили циклом по массиву, суммируя k следующих или предыдущих соседей каждого эл-та.
Для оптимального решения за O(n) - используем алгоритм "скользящего окна" с двумя указателями. Размер окна (window_size) равен abs(k).
Окно двигается вправо: добавляем правый эл-т, и если размер окна превысил window_size - сдвигаем левую границу, удаляя левый эл-т.

Так как массив круговой, для нахождения корректного индекса используем операцию взятия по модулю (% n), что позволит вернуться в начало при выходе за правую границу или перейти в конец при выходе за левую границу.
Если k > 0: окно равно следующим k эл-м; эл-т, для которого считаем сумму, стоит слева от окна.
Если k < 0: окно равно предыдущим |k| эл-м; эл-т, для которого считаем сумму, стоит справа от окна.

Инициализируем массив res для хранения результата и заполняем нулями.
window_sum - сумма внутри окна
l - левая граница окна
r - правая граница окна

Если k равен нулю:
- возвращаем res (все эл-ты уже равны 0).

Двигаем окно правым указателем, проходя n + window_size - 1 итераций (где первые window_size итераций строим окно нужного размера, и на последней из них записываем первый ответ, а оставшиеся n - 1 итераций - сдвигаем окно, записывая ответы для остальных эл-в):
- Добавляем правый эл-т в окно.

- Если окно переполнилось (достигло window_size + 1):
- убираем один эл-т слева;
- сдвигаем l вправо.

- Если окно достигло размера window_size, записываем ответ:
- если k положительный: окно начинается с l => записываем ответ для индекса (l-1) % n
- если k отрицательный: окно заканчивается на r => ответ для индекса (r+1) % n

Возвращаем res.

Сложность
O(n) - по времени (проходим по массиву один раз)
O(n) - по памяти (храним некоторое кол-во переменных и массив res, равный длине входного массива)

Код
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
res = [0] * n

if k == 0:
return res

window_size = abs(k)
l = 0
window_sum = 0

for r in range(n + window_size - 1):
window_sum += code[r % n]

if r - l + 1 > window_size:
window_sum -= code[l % n]
l = (l + 1) % n

if r - l + 1 == window_size:
if k > 0:
res[(l - 1) % n] = window_sum
if k < 0:
res[(r + 1) % n] = window_sum

return res

@algoses