Defuse the Bomb — LeetCode 1652 Python Solution

The problem

You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length of n and a key k.

Example

Input

code = [5,7,1,4], k = 3

Output

[12,10,16,13]

Explanation

Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Python solution

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        ans = [0] * n
        if k == 0:
            return ans
        for i in range(n):
            if k > 0:
                for j in range(i + 1, i + k + 1):
                    ans[i] += code[j % n]
            else:
                for j in range(i + k, i):
                    ans[i] += code[(j + n) % n]
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1652. Defuse the Bomb is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems