Brute Force
"""
tc O(N) sc O(N)
i
0 1 2 3
^ ^
k = 2
i-1-k
n-1-k = 4-1-3
k = 3
i - 3 +6 = psum[-1]-psum[1-3+6-1]
i - k + n - 1 3
"""
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
res = [0] * n
if k == 0 :
return res
psum = [0]*n
psum[0] = code[0]
for i in range(1,n):
psum[i] = psum[i-1]+code[i] # A[1]+A[2] = psum[2] - psum[0]
if k > 0 :
for i in range(n):
res[i] = psum[i+k] - psum[i] if i+k < n else psum[(i+k)%n] + psum[-1] - psum[i]
elif k < 0 :
k = - k
for i in range(n):
if i-1>= 0 and i-1-k < 0 :
res[i] = psum[i-1] + psum[-1] - psum[i-k+n-1]
elif i-1<0:
res[i] = psum[-1] -psum[n-1-k]
else:
res[i] = psum[i-1] - psum[i-1-k]
return res
Optimization: Sliding Window
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
"""
1. define boundry (set differently based on k < 0 , k > 0 )
2. preprocess accumutive sum within boundry
3. update left ptr and right ptr
tc O(N) sc O(1)
"""
n = len(code)
res = [0]* n
if k == 0 :
return res
left,right = 1,k
if k < 0 :
k = -k
left,right = n-k,n-1
sum = 0
for i in range(left,right+1): # get first k sum
sum += code[i]
for j in range(n):
res[j] = sum # update res first before move left ptr forward
sum -= code[left%n]
left += 1
right += 1
sum += code[right%n]
return res